Jump to content
  • entries
    55
  • comments
    2
  • views
    59,207

Güç Pareto Evrimsel Algoritma (SPEA)


Doğuhan ELMA

216 views

Güç Pareto Evrimsel Algoritma (SPEA), Zitzler ve Thiele tarafından 1999 yılında geliştirilen ve birçok hedefi olan optimizasyon problemlerini çözmek için tasarlanmış bir evrimsel algoritmadır. Pareto çözümlerini bulmak için kullanılır ve daha sonra Zitzler ve ekibi tarafından geliştirilmiş SPEA2'ye temel oluşturmuştur.

Bu algoritma, çok hedefli optimizasyon problemlerinin çözümüne bir yaklaşım sunar ve belirli bir çözümün kalitesini belirlemek için bir fitness fonksiyonu kullanır. Pareto optimizasyonunda, bir çözümün "fit" olup olmadığına karar vermek genellikle zordur çünkü genellikle bir hedefin optimizasyonu, diğerlerinin aleyhine gerçekleşir. SPEA, bu sorunu çözer ve pareto-optimal çözümler setini bulmaya yardımcı olur.

SPEA'nın çalışma prensibi şu şekildedir:

1. Başlangıçta, rastgele oluşturulan bir popülasyon (genellikle P olarak gösterilir) ve bir dış (arşiv) popülasyon (genellikle A olarak gösterilir) vardır.

2. Her birey için, hangi çözümlerin domine ettiği ve hangi çözümlerin tarafından domine edildiği belirlenir. Bu bilgiler daha sonra fitness değerlerini hesaplamak için kullanılır.

3. Fitness değerleri, bir çözümün domine ettiği diğer çözümlerle ilişkilidir. Bir çözüm, domine ettiği çözümler sayısına göre bir fitness değeri alır.

4. Arşiv güncellenir: fitness değeri eşik değerinden düşük olan bireyler arşive eklenir. Eşik değeri genellikle mevcut arşiv boyutuna ve maksimum arşiv boyutuna bağlıdır.

5. Arşiv boyutu maksimum boyutu aşarsa, arşivdeki en düşük fitness değerine sahip bireyler çıkarılır.

6. Arşivden bireyler seçilir ve genetik operatörler (çaprazlama, mutasyon) uygulanır. Bu, yeni bir popülasyon oluşturur.

7. Yeni popülasyon fitness değerlerine göre değerlendirilir ve arşiv güncellenir.

Bu işlemler belirli bir durma kriteri (örneğin maksimum nesil sayısı) karşılanana kadar tekrarlanır.

Sonuç olarak, SPEA, çok hedefli optimizasyon problemlerini çözmek için güçlü ve etkili bir algoritmadır. Farklı hedefler arasında denge sağlar ve çözüm setini pareto-optimal çözümlerle doldurur.

 

import random
import numpy
from deap import algorithms
from deap import base
from deap import creator
from deap import tools

creator.create("FitnessMulti", base.Fitness, weights=(-1.0, -1.0))
creator.create("Individual", list, fitness=creator.FitnessMulti)

toolbox = base.Toolbox()

toolbox.register("attr_float", random.random)
toolbox.register("individual", tools.initRepeat, creator.Individual, toolbox.attr_float, n=2)
toolbox.register("population", tools.initRepeat, list, toolbox.individual)

def evaluate(individual):
    a = sum((x-0.5)**2 for x in individual)
    b = sum((x-0.5)**2 for x in individual)
    return a, b

toolbox.register("evaluate", evaluate)
toolbox.register("mate", tools.cxSimulatedBinaryBounded, low=0.0, up=1.0, eta=20.0)
toolbox.register("mutate", tools.mutPolynomialBounded, low=0.0, up=1.0, eta=20.0, indpb=1.0/2)
toolbox.register("select", tools.selSPEA2)

def main():
    random.seed(64)
    MU = 100
    LAMBDA = 100
    CXPB = 0.7
    MUTPB = 0.2
    NGEN = 250
    pop = toolbox.population(n=MU)
    hof = tools.ParetoFront()
    stats = tools.Statistics(lambda ind: ind.fitness.values)
    stats.register("avg", numpy.mean, axis=0)
    stats.register("std", numpy.std, axis=0)
    stats.register("min", numpy.min, axis=0)
    stats.register("max", numpy.max, axis=0)

    pop, logbook = algorithms.eaMuPlusLambda(pop, toolbox, MU, LAMBDA, CXPB, MUTPB, NGEN, stats,
                                             halloffame=hof)

    return pop, logbook, hof

if __name__ == "__main__":
    pop, logbook, hof = main()
    print("En iyi bireyler:")
    for individual in hof:
        print(individual)

Bu örnekte, SPEA2 algoritması bir iki hedefli optimizasyon problemi üzerinde çalıştırılmaktadır. İki hedefin her ikisi de minimize edilmeye çalışılır ve bu hedefler bir bireyin fitness değerlerini belirler. Bireyler 2 boyutlu bir arama alanında yer alırlar ve her bir birey iki rastgele oluşturulan reel sayıyı içerir.

Algoritma, 250 nesil boyunca çalıştırılır ve her nesil boyunca, popülasyon SPEA2 seçim işlemi ile seçilir ve çaprazlama ve mutasyon işlemlerine tabi tutulur. Bu işlemler sonucunda oluşturulan yeni bireyler mevcut popülasyona eklenir.

Bu süreç, belirtilen nesil sayısı (NGEN) ulaşıncaya kadar tekrarlanır. Bu kodda hedef değerlerin ne olduğunu ve bireylerin nasıl oluşturulduğunu ve değerlendirildiğini ayarlama yeteneğine sahip olacaksınız. Bu, farklı problemler üzerinde çalışabilme yeteneği sağlar.

algorithms.eaMuPlusLambda fonksiyonu, popülasyonu, istatistiksel log'u ve Pareto cephedeki (yani, en iyi bireylerin yer aldığı) bireyleri döndürür.

İstatistiksel log (logbook), her neslin istatistiklerini içerir: ortalamayı (avg), standart sapmayı (std), minimum (min) ve maksimum (max) fitness değerlerini. Bu değerler, algoritmanın nasıl geliştiğini takip etmenizi sağlar.

ParetoFront nesnesi (hof), en iyi bireyleri saklar. Bunlar, diğer bireylerle karşılaştırıldığında hiçbir hedefte kötüleşmeyen ve en az bir hedefta iyileşen bireylerdir.

0 Comments


Recommended Comments

There are no comments to display.

Guest
Add a comment...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...