Şu yazıyı okuyorsunuz: Python’da Genetik Algoritmayla Nesnelerden Kaçınmayı Optimize Etme: Yapay Zekaya Doğru
İlk olarak Yapay Zekaya Doğru’da yayınlandı.
Doğa uzun zamandır optimizasyon ve problem çözme teknikleri için bir ilham kaynağı olarak hizmet etmiştir. Doğal evrimi taklit eden yaklaşımlardan biri de genetik algoritmadır.
Genetik algoritma, optimale yakın veya optimal çözümleri keşfetmek için doğal seçilim ve genetik kalıtım ilkelerinden yararlanan bir meta-sezgiseldir. Her genetik algoritmanın temelinde a kavramı bulunur. Seçme, çaprazlama ve mutasyon gibi genetik evrimi simüle eden süreçler aracılığıyla bir dizi kromozom sürekli olarak geliştirilir. Kötü performans gösteren kromozomlar kademeli olarak çıkarılır, daha iyi performans gösterenler ise korunur. Kromozomlarınki, etkinliğinin bir ölçüsü olarak hizmet eder. Olarak bilinen birkaç yinelemeden sonra, tek bir kromozom veya kromozom grubu, sonunda verilen problem için optimal veya optimale yakın çözüm olarak ortaya çıkar.
Genetik algoritmanın verimliliği bir tartışma konusu olsa da, basit uygulaması onu modelciler arasında popüler bir seçim haline getirmiştir. Bu algoritma, mühendislik, bilgisayar bilimi ve finans dahil olmak üzere çeşitli alanlarda uygulamalar bulmuş ve burada genellikle hesaplama açısından zorlayıcı veya çözülmesi zor olan optimizasyon sorunlarını çözmüştür.
Bu makale iki boyutlu engellerden kaçınma probleminde genetik algoritmanın ilkelerini göstermektedir. Kurulumumuz, soldan sağa yatay olarak hareket eden hareketli bir nesneden (araba olarak bilinir) oluşur. Ayrıca dikey olarak ilerleyen ve aracın yolunu kapatabilecek hareketli engeller bulunmaktadır. Tartışmamızın ana odağı algoritmanın kendisi, özellikle de onun temel operatörleri: seçme, çaprazlama ve mutasyon üzerindedir. Simülasyon kurulumunun ayrıntılı açıklaması gelecekteki tartışmalarda ayrıca ele alınacaktır.
Kromozom ve uygunluk tanımı
Her genetik algoritmada kromozomlar ve uygunluk kavramları çok önemli bir rol oynar. Bir kromozom esasen, genellikle bitlerle (0 ve 1) ifade edilen bir değerler dizisidir, ancak spesifik soruna bağlı olarak tamsayılar olarak da temsil edilebilir. Kromozom verilen problemin çözüm alanını temsil eder.
Öte yandan uygunluk, bir çözümün performansını değerlendiren bir metrik veya fonksiyon görevi görür. Belirli bir kromozomun veya çözümün eldeki sorunu ne kadar iyi çözdüğünü belirler. Uygunluk fonksiyonu, optimizasyon problemi bağlamında kromozomun uygunluğunun veya etkinliğinin niceliksel bir ölçümünü sağlar.
Basitleştirilmiş kurulumumuzda, bir kromozomu simülasyon boyunca arabanın ivmesinin temsili olarak tanımlıyoruz. Kromozom içindeki her değer, belirli bir zamandaki ivmeye karşılık gelir. Bir kromozom örneğini ele alalım:
>>> ivme = [1, 2, -1, 2, 3]
Bu senaryoda simülasyonumuz beş zaman dilimini kapsamaktadır. Kromozom içindeki ivme değerleri şu şekildedir: İlk kare için 1, ikinci kare için 2, üçüncü kare için -1 vb. Hızlanmayı kromozom olarak seçtik çünkü kat edilen mesafenin ikinci türevidir ve ivmenin iki kez entegre edilmesi arabaya yumuşak hareket verir.
Daha sonra, uygunluğu arabanın kat ettiği normalleştirilmiş mesafe olarak tanımlıyoruz. Simülasyon, araç bir engele çarptığında veya maksimum zaman dilimi sayısına ulaştığında sona erer. Bu uygunluk tanımının amacı, algoritmanın, engelleri başarılı bir şekilde aşabilen arabalar üreten kromozomlara (hızlanma dizileri) öncelik vermesini teşvik etmektir. İdeal olarak, başarılı bir senaryo, arabanın tüm parkuru belirli bir zaman dilimi içinde tamamlayıp çarpışma olmadan tüm engellerden başarılı bir şekilde kaçındığında ortaya çıkar.
Genetik algoritma yapısı
Genetik algoritmamızın adımlarını şu şekilde özetleyebiliriz:
- Başlatma: Rastgele bir dizi kromozom oluşturarak başlayın.
- Uygunluk Hesaplaması: Her bir kromozomun uygunluğunu değerlendirin ve en iyi performans gösteren kromozomu belirleyin.
- Uygunluk olasılığının hesaplanması: Her bir kromozom için uygunluk olasılığını belirleyin.
- Seçim: Uygunluk olasılıklarına göre daha güçlü kromozomların bir alt kümesini seçin ve daha zayıf kromozomları eleyin. Silinen kromozomları yeni oluşturulan rastgele kromozomlarla değiştirin.
- Çaprazlama: Kromozom çiftlerini seçin ve karşılık gelen dizi konumlarında () segmentleri değiştirin.
- Mutasyon: Kromozom seti içindeki değerleri rastgele değiştirir.
- Sonlandırma koşullarından biri karşılanana kadar 2’den 6’ya kadar olan adımları tekrarlayın: ya en iyi performans gösteren kromozomla ilişkili araba rotayı çarpışmadan ve verilen süre içinde tamamlar ya da maksimum nesil sayısına ulaşılır.
Kurulumumuzda sabit sayıda kromozomla, özellikle her sette 50 kromozomla çalışıyoruz. Ayrıca simülasyonun çözüm bulamadan süresiz olarak çalışmasını önlemek için maksimum nesil sayısını 50’ye ayarladık. Maksimum simülasyon süresi 400 zaman dilimi olarak ayarlanmıştır.
Fiziksel yetenek
Aşağıdaki şekil, 0. nesildeki 50 kromozomluk başlangıç setinden en iyi performans gösteren kromozomdan türetilen en iyi performansa sahip arabanın yörüngesini göstermektedir. Bu kromozom üzerindeki ivme değerleri rastgele oluşturulur. Ancak bu özel durumda araba dokuzuncu engelle çarpışarak simülasyonun sonlandırılmasına yol açar. Bu senaryoda araba başına kat edilen toplam mesafe 18’dir (isteğe bağlı mesafe birimlerinde). Sonuç olarak, bu en iyi performans gösteren kromozomun uygunluk puanı yaklaşık olarak 7,5/18 = 0,417’dir.
Uygunluk Olasılığı
Algoritmanın özüne geçmeden önce her bir kromozomun uygunluk olasılığını hesaplamamız gerekir. Uygunluk olasılığı, her bir kromozomun set içindeki diğerlerine göre ne kadar iyi performans gösterdiğinin bir göstergesi olan uygunluk değerlerinin normalleştirilmesiyle belirlenir. Bu olasılıklar daha sonra algoritmanın seçim aşamasında kullanılır.
Üç kromozom için uygunluk değerlerini ve ilgili uygunluk olasılıklarını gösteren aşağıdaki örneği düşünün. Bu senaryoda, kromozom 1, kromozom 2 ve kromozom 3’ün iki katı performans gösterir.
Aşağıda, belirli bir kromozom seti için uygunluk değerlerini (normalleştirilmiş mesafeler) ve uygunluk olasılıklarını hesaplamaya yönelik yöntemler içeren bir fitness sınıfını gösteren bir kod pasajı bulunmaktadır:
uygunluk sınıfı:def __init__(ser,distances: numpy.ndarray,):“”” :param distances: Arabanın her kromozom için kat ettiği mesafe.“””self.distances = mesafeler
def normalized_distance(self) -> numpy.ndarray:“””Maksimum mesafe üzerindeki seyahat mesafelerini uygunluk olarak kullanın. ‘Uygunlukların’ biçimi (N_kromozom,) şeklindedir. `c.max_distance` = 18.“””self.distances / c.max_distance değerini döndürür
@staticmethoddef fitness_probaibility(fitnesses: numpy.ndarray) -> numpy.ndarray:“””Uyumlu olma olasılığını hesaplayın.“””p_fitness = numpy.asarray(aptitudes) / numpy.sum(aptitudes)return p_fitness
Seçim
Genetik algoritmanın ilk operatörü, daha ileri işlemler için setten iyi performans gösteren kromozomların seçilmesinden oluşan seçimdir. Çeşitli seçim yöntemleri mevcuttur; bunlardan bazıları probleme özeldir, bazıları ise doğası gereği daha geneldir. Kurulumumuzda, bir kromozomu seçme olasılığının onun uygunluk olasılığıyla doğru orantılı olduğu yaygın olarak kullanılan bir yaklaşım olan rulet çarkı seçim yöntemini kullanıyoruz.
Rulet çarkı seçim süreci, orijinal settekiyle aynı sayı korunarak istenilen sayıda kromozom elde edilene kadar tekrarlanır. Bu yöntemin kullanılmasıyla, uygunluk olasılığı daha yüksek olan kromozomların seçilme şansı daha yüksek olur ve bu da onların üstün performansını yansıtır.
Yukarıdaki üç kromozomlu örnekte, rulet çarkı seçim yöntemini kullanarak seçim sürecini göstereceğiz. Bu durumda, üç kromozomdan oluşan yeni bir set elde etmek için üç çizim yaparak tekrarlı olarak setten kromozomları çıkarıyoruz. Kromozom 1 en yüksek uygunluk olasılığına sahip olduğundan rulet çarkı seçim sürecinde seçilme şansı en yüksektir.
Çekilişleri simüle edelim: Üç çekilişten sonra, üç kromozomdan oluşan yeni bir setimiz olur: kromozom 1, kromozom 1 (tekrarlanan seçim) ve kromozom 3. Seçim süreci, uygunluk olasılığı daha yüksek olan kromozomları tercih eder, bu da daha yüksek bir olasılık ile sonuçlanır. 1. kromozomun birden çok kez seçilmesi.
Aşağıda, numpy.random.choice() işlevini kullanarak rulet çarkı seçme yöntemini uygulayan bir seçme sınıfını gösteren bir kod parçacığı bulunmaktadır:
Sınıf seçimi:def __init__(ser,p_fitness: numpy.ndarray,accelerations: numpy.ndarray,):“”” :param p_fitness: Uygunluk olasılıkları.:param ivmeler: Hızlanmalar (aka kromozomlar).“””self .p_fitness = p_fitnessself .ivmeler = ivmeler
def roulette_wheel(self) -> numpy.ndarray:“””Rulet çarkı aracılığıyla seçim. `c.N_chromosome` = 50.“””chromosome_to_hold_indexes = numpy.random.choice(c.N_chromosome, c.N_chromosome, True, self.p_fitness)return self.speedups[chromosome_to_keep_indices]
Geçmek
Seçim sürecinden sonra, yeni kromozom seti çaprazlanır ve bu, önceden seçilen kromozomlarla benzerlikleri koruyan yeni çözümlerin üretilmesini içerir. Çaprazlamada aleller bir dizi kromozom arasında değiştirilir. Olası bir çaprazlama işlemini göstermek için üç kromozomlu örneğimizi gözden geçirelim:
Bu örnekte aleller, bir kromozom çifti arasındaki belirli pozisyonlarda değiştirilir; örneğin kromozom 1’deki ikinci değer ve kromozom 3’teki ikinci değerin yanı sıra kromozom 2’deki beşinci değer ve kromozom 3’teki beşinci değer gibi. Sonuçta ortaya çıkan alellerin aynı olacağı konumlarda kromozom 1 ile kromozom 2 arasında çaprazlama da meydana gelebilir. Örneğin, 1. kromozomdaki üçüncü değer ile 2. kromozomdaki üçüncü değer aynıysa, o konumda yine de çaprazlama gerçekleşebilir.
Çaprazlamayı uygulamak için çaprazlama olasılığını tanımlayarak başlarız. Tipik olarak, daha önce seçilen kromozomların nispeten sağlam kalmasını sağlamak ve yeni kromozom setine stokastisite eklemeye devam etmek için bu olasılığa küçük bir değer atanır. Algoritmamızda çaprazlama olasılığını 0,2 olarak ayarladık.
Aşağıda Crossover sınıfını gösteren bir kod pasajı bulunmaktadır. Simple_crossover yöntemi çaprazlama için belirli sayıda kromozomu rastgele seçer. Seçilen her kromozom çifti için, değiş tokuş edilecek rastgele bir alel seçilir.
sınıf geçişi:def __init__(self, ivmeler: numpy.ndarray):self.accelerations = ivmeler
def simple_crossover(self) -> numpy.ndarray:“””İkili olmayan basit geçiş. `c.p_crossover` = 0,2.“””N_crossover = int(c.p_crossover * c.N_kromozomu)if N_crossover % 2 != 0:N_crossover -= 1
random_indexes = numpy.random.choice(c.N_chromosome, size=N_crossover, replacement=False)
# Aralıktaki n için ön ve arka kromozom çiftlerinin çaprazlanması (int (N_crossover / 2)): a, b = random_indexes[n]rastgele_indeksler[N_crossover – n – 1]ön = otomatik.hızlanmalar[a].copy()back = otomatik hızlanmalar[b].copy() dilim = numpy.random.choice(c.N_frame, size=2, replacement=False)otomatik hızlar[a][portion[0] : porsiyon[1]]= arka[portion[0] : porsiyon[1]]otomatik hızlanmalar[b][portion[0] : porsiyon[1]]= ön[portion[0] : porsiyon[1]]
otomatik hızlanmaları döndür
Mutasyon
Genetik algoritmadaki son operatör, kromozomların içindeki değerleri değiştirerek rastgeleliği ortaya çıkaran bir mutasyondur. Üç kromozom örneğimize dönecek olursak, bir mutasyon işlemi aşağıdaki güncellenmiş kromozom setine yol açabilir:
Bu örnekte dört mutasyon meydana gelir: Kromozom 1’in ilk değeri 1’den 4’e mutasyona uğrar, kromozom 2’nin üçüncü değeri -1’den 0’a mutasyona uğrar, kromozom 3’ün ilk değeri 1’den 0’a mutasyona uğrar ve dördüncü değeri -1’den 0’a mutasyona uğrar. El kromozomu 3, 4’ten 3’e mutasyona uğrar.
Mutasyonu genetik algoritmaya dahil etmek için mutasyon olasılığına ihtiyacımız var. Aşırı mutasyon değerli bilgilerin kaybına yol açabileceğinden mutasyonları uygularken bir denge kurmak önemlidir. Bizim durumumuzda 0,05 mutasyon olasılığını kullanıyoruz.
Aşağıda simple_mutation yöntemini içeren Mutation sınıfı bulunmaktadır. Bu yöntem, uygulanacak mutasyon sayısını belirler ve buna göre kromozomları ve mutasyon yerlerini seçer. Daha sonra rastgele oluşturulan değerler mutasyon konumlarına atanır.
Mutasyon sınıfı:“””Mutasyonla ilgili algoritmayı işleyecek sınıf“””
def __init__(self, ivmeler: numpy.ndarray):self.accelerations = ivmeler
def simple_mutation(self):“””Basit ikili olmayan mutasyon. ‘c.p_mutation’ = 0,02 ve ‘c.max_acceleration’ = 5.“””N_mutation = int(c.N_chromosome * c.N_frame * c.p_mutation)
# Y (hangi kromozomda) ve
i için (N_mutasyon):x, y = mutasyon_x aralığında[i]mutasyon_y[i]otomatik hızlanmalar[y, x] = (numpy.random.randint(-c.max_acceleration, c.max_acceleration + 1))
otomatik hızlanmaları döndür
Sonuç ve özet
(Neredeyse) optimal bir çözüme ulaşana kadar yinelemeli seçim, çaprazlama ve mutasyon sürecine devam ediyoruz; bu bizim durumumuzda arabanın engelli parkuru başarıyla tamamladığı zamandır. Aşağıdaki şekil otomobilin 47. nesilde başarıyla tamamlandığını göstermektedir:
Yineleme 47’den önceki nesiller, en iyi performans gösteren çözümü bulmak için kromozom setini geliştiren ve iyileştiren algoritmayı içerir. Algoritma, seçme, çaprazlama ve mutasyonun tekrar tekrar uygulanmasıyla, yavaş yavaş arabanın rotada başarılı bir şekilde ilerlemesini sağlayan kromozomlara odaklanıyor. Optimal çözüme ulaşmak için gerekli nesil sayısı, problemin karmaşıklığı, popülasyonun büyüklüğü, seçim, çaprazlama ve mutasyon operatörlerinin etkinliği gibi faktörlere bağlı olarak değişebilir.
Sonuç olarak, nesne kaçınma optimizasyon problemini çözmek için genetik algoritmanın başarılı bir şekilde uygulandığını gösterdik. Yinelemeli seçim, çaprazlama ve mutasyon süreciyle genetik algoritmanın, otomobilin ardışık nesiller boyunca hareketli engeller arasında gezinme yeteneğini geliştirmede etkili olduğu kanıtlandı.
Ancak genetik algoritmanın sınırlamalarının bilinmesi önemlidir. Bir sınırlama, problem konfigürasyonundaki değişikliklere uyum sağlama konusundaki eksikliğidir. Belirli bir engel konfigürasyonundan elde edilen en iyi performansa sahip kromozom, konfigürasyon değiştirildiğinde optimal olmayabilir ve hatta etkili olmayabilir. Yeni ayarları ele almak için, aracın değişiklikleri öğrenmesine ve bunlara uyum sağlamasına olanak sağlamak amacıyla simülasyonun baştan tekrar çalıştırılması gerekecektir. Ayrıca genetik algoritmanın etkinliği büyük ölçüde kromozomların ve uygunluğun nasıl tanımlandığına bağlıdır. Doğru ve anlamlı optimizasyon sonuçları sağlamak için uygun kromozom temsillerinin ve uygunluk ölçümlerinin tasarlanmasına dikkat edilmelidir.
Bu sınırlamalara rağmen genetik algoritma, karmaşık ve yapılandırılmamış sorunları çözme potansiyelini göstermiştir. Geleneksel yaklaşımlarla kolaylıkla elde edilemeyecek içgörüler ve çözümler sağlayarak, birden çok alanda optimizasyon için değerli bir araç olarak hizmet eder. Uygun parametre ayarı ve probleme özel uyarlamalar ile genetik algoritma, çok çeşitli optimizasyon senaryolarında optimuma yakın çözümler bulmak için güçlü bir araç olabilir.
Towards AI aracılığıyla yayınlandı
