Genetik Algoritmalar: Doğal Seleksiyon ile Arama ve Optimizasyon

Genetik Algoritmalar Nelerdir?

Son birkaç yılda, Yapay Zeka (AI) hakkında müthiş bir vızıltı oldu. Google, Apple ve Microsoft gibi büyük şirketler bu konu üzerinde aktif olarak çalışıyor. Aslında, AI birçok hedefi, yaklaşımı, aracı ve uygulamayı kapsayan bir şemsiyedir. Genetik Algoritmalar (GA), birçok olası çözümde akıllı arama yapmak için kullanılan araçlardan sadece biridir.

GA, doğal evrimde mevcut olan ilkelere dayalı bir meta-sezgisel arama ve optimizasyon tekniğidir. Daha geniş bir evrimsel algoritma sınıfına aittir.

GA, problem için bir dizi potansiyel çözüm olan bir kromozom popülasyonunu korur. Buradaki fikir, “evrim”in, doğal seleksiyona benzer şekilde, birbirini izleyen birkaç nesilden sonra problem için optimal bir çözüm bulacağıdır.

GA üç evrimsel süreci taklit eder: seçim, gen çaprazlaması ve mutasyon.

Doğal seçilime benzer şekilde, GA seçiminin merkezi kavramı uygunluktur. Daha uygun olan kromozomların hayatta kalma şansı daha yüksektir. Uygunluk, kromozom tarafından temsil edilen çözümün kalitesini ölçen bir fonksiyondur. Özünde, popülasyon içindeki her kromozom girdi parametrelerini temsil eder. Örneğin, sorununuz ticarette fiyat ve hacim gibi iki girdi parametresi içeriyorsa, her kromozom mantıksal olarak iki öğeden oluşacaktır. Elementlerin kromozom içinde nasıl kodlandığı ise ayrı bir konu.

Seçim sırasında, kromozomlar üreme için ebeveyn çiftleri oluşturur. Her çocuk ebeveynlerinden özellikler alır. Temel olarak, çocuk, ebeveynlerinden gelen özelliklerin bir yeniden birleşimini temsil eder: Bazı özellikler bir ebeveynden, bazıları da diğerinden alınır. Rekombinasyona ek olarak, bazı özellikler mutasyona uğrayabilir .

Daha uygun kromozomlar daha fazla çocuk ürettiğinden, sonraki her nesil daha iyi bir zindeliğe sahip olacaktır. Bir noktada, bir nesil, problemimiz için yeterince iyi bir çözümü temsil edecek bir kromozom içerecektir.

GA güçlüdür ve karmaşık problemler için geniş çapta uygulanabilir. Geleneksel optimizasyon teknikleriyle çözülmesi oldukça zor olan geniş bir optimizasyon problemi sınıfı vardır. Genetik algoritmalar, çözümü yaklaşık olarak optimal olan verimli algoritmalardır. İyi bilinen uygulamalar arasında çizelgeleme, ulaşım, yönlendirme, grup teknolojileri, yerleşim tasarımı, sinir ağı eğitimi ve daha birçokları yer alır.

İşleri Uygulamak

İnceleyeceğimiz örnek, GA'nın “Merhaba Dünyası” olarak kabul edilebilir. Bu örnek başlangıçta J. Freeman tarafından Mathematica ile Sinir Ağlarını Simülasyonda verildi. Mitsuo Gen ve Runwei Cheng'in Genetik Algoritmalar ve Mühendislik Tasarımından aldım.

Kelime Eşleştirme Problemi, genetik bir algoritma ile bir ifade geliştirmeye çalışır. Başlangıçta, algoritmanın rastgele oluşturulmuş harf listelerinden "olmak ya da olmamak" ifadesini "tahmin etmesi" gerekiyordu.

Listede [boşluk hariç] 13 konumun her biri için 26 olası harf olduğundan, doğru ifadeyi tamamen rastgele bir şekilde alma olasılığımız (1/26)^13=4.03038×10-19, yani yaklaşık olarak bir [quintillion] üzerinden iki şans (Gen & Chong, 1997).

Burada sorunu biraz daha geniş tanımlayarak çözümü daha da zorlaştıracağız. İngilizce diliyle veya belirli bir ifadeyle sınırlı olmadığımızı varsayalım. Sonunda herhangi bir alfabeyle, hatta herhangi bir sembol kümesiyle uğraşabiliriz. Dil bilgimiz yok. Herhangi bir dil olup olmadığını bile bilmiyoruz.

Diyelim ki rakibimiz boşluk da dahil olmak üzere keyfi bir ifade düşündü. Alfabedeki tümcenin uzunluğunu ve sembollerin sayısını biliyoruz. Elimizdeki tek bilgi bu. Her tahminden sonra rakibimiz bize kaç harfin yerinde olduğunu söyler.

Her kromozom, alfabedeki sembollerin bir dizi indeksidir. İngiliz alfabesinden bahsediyorsak, 'a' 0, 'b' 1, 'c' 2 ile temsil edilecektir. Örneğin, “olmak” kelimesi [4, 1] olarak temsil edilecektir.

Tüm adımları Java kod parçacıkları aracılığıyla göstereceğiz, ancak her adımı anlamak için Java bilgisi gerekli değildir.

Genetik Algoritma Çekirdeği

Genetik algoritmanın genel bir uygulamasıyla başlayabiliriz:

 public void find() { // Initialization List<T> population = Stream.generate(supplier) .limit(populationSize) .collect(toList()); // Iteration while (!termination.test(population)) { // Selection population = selection(population); // Crossover crossover(population); // Mutation mutation(population); } }

Bu, her GA'nın az ya da çok oluşturduğu basit adımlar dizisidir. Başlatma adımında, bir başlangıç ​​cümlecik popülasyonu oluştururuz. Popülasyonun boyutu, populationSize tarafından belirlenir. İfadenin nasıl oluşturulduğu, supplier uygulamasına bağlıdır.

Yineleme adımında, while döngüsünün testinde sonlandırma koşulları karşılanana kadar popülasyonu geliştiririz. Sonlandırma koşulları, hem nesil sayısını hem de popülasyondaki ifadelerden birinin tam eşleşmesini içerebilir. termination , kesin bir uygulamayı kapsar.

Her yinelemede tipik GA adımlarını gerçekleştiririz:

1. Popülasyon üzerinde kromozom uygunluğuna dayalı bir seçim yapın.
2. Çaprazlama işlemi ile yeni bir "nesil" üretin.
3. Bazı cümlelerde bazı harflerin yeniden birleşimini gerçekleştirin.

Algoritmanın özü çok basit ve alandan bağımsızdır. Tüm problemler için aynı olacaktır. Ayarlamanız gereken şey, genetik operatörlerin uygulanmasıdır. Daha sonra, daha önce bahsedilen GA operatörlerinin her birine yakından bakacağız.

seçim

Zaten bildiğimiz gibi, seçim, mevcut kromozomların ardıllarını bulma sürecidir - problemimize daha uygun kromozomlar. Seçim sırasında, daha iyi uygunluk gösteren kromozomların hayatta kalma şansının daha yüksek olduğundan emin olmamız gerekir.

 private List<T> selection(List<T> population) { final double[] fitnesses = population.stream() .mapToDouble(fitness) .toArray(); final double totalFitness = DoubleStream.of(fitnesses).sum(); double sum = 0; final double[] probabilities = new double[fitnesses.length]; for (int i = 0; i < fitnesses.length; i++) { sum += fitnesses[i] / totalFitness; probabilities[i] = sum; } probabilities[probabilities.length - 1] = 1; return range(0, probabilities.length).mapToObj(i -> { int index = binarySearch(probabilities, random()); if (index < 0) { index = -(index + 1); } return population.get(index); }).collect(toList()); }

Bu uygulamanın arkasındaki fikir şudur: Popülasyon, sayısal eksende birbirini izleyen aralıklar olarak temsil edilir. Tüm popülasyon 0 ile 1 arasındadır.

Bir kromozomun aldığı aralığın parçası, uygunluğu ile orantılıdır. Bu, daha uygun bir kromozomun daha büyük bir yığın almasıyla sonuçlanır. Sonra rastgele 0 ile 1 arasında bir sayıya bakarız ve o sayıyı içeren bir aralık buluruz. Açıkçası, daha büyük aralıkların seçilme şansı daha yüksektir ve bu nedenle daha uygun kromozomların hayatta kalma şansı daha yüksektir.

Uygunluk fonksiyonu hakkında detayları bilmediğimiz için uygunluk değerlerini normalleştirmemiz gerekiyor. Uygunluk işlevi, bir kromozomu kromozomun uygunluğunu temsil eden keyfi bir çifte dönüştüren fitness ile temsil edilir.

Kodda, popülasyondaki tüm kromozomlar için uygunluk oranlarını buluyoruz ve ayrıca toplam uygunluğu da buluyoruz. for döngüsü içinde, toplam uygunluk tarafından küçültülmüş olasılıklar üzerinde kümülatif bir toplam gerçekleştiririz. Matematiksel olarak, bu, son değişkenin 1 değerine sahip olmasıyla sonuçlanmalıdır. Kayan noktanın kesin olmaması nedeniyle, bunu garanti edemeyiz, bu yüzden emin olmak için 1'e ayarladık.

Son olarak, giriş kromozomlarının sayısına eşit sayıda kez rastgele bir sayı üretir, sayıyı içeren bir aralık bulur ve ardından karşılık gelen kromozomu seçeriz. Fark edebileceğiniz gibi, aynı kromozom birden çok kez seçilebilir.

Karşıdan karşıya geçmek

Şimdi "üremek" için kromozomlara ihtiyacımız var.

 private void crossover(List<T> population) { final int[] indexes = range(0, population.size()) .filter(i-> random() < crossoverProbability) .toArray(); shuffle(Arrays.asList(indexes)); for (int i = 0; i < indexes.length / 2; i++) { final int index1 = indexes[2 * i]; final int index2 = indexes[2 * i + 1]; final T value1 = population.get(index1); final T value2 = population.get(index2); population.set(index1, crossover.apply(value1, value2)); population.set(index2, crossover.apply(value2, value1)); } }

Önceden tanımlanmış olasılık crossoverProbability ile, yetiştirme için ebeveynleri seçiyoruz. Seçilen ebeveynler karıştırılır ve herhangi bir kombinasyonun gerçekleşmesine izin verilir. Ebeveyn çiftlerini alıyoruz ve crossover operatörünü uyguluyoruz. Popülasyonun boyutunu aynı tutmamız gerektiğinden, operatörü her çift için iki kez uygularız. Çocuklar, popülasyonda ebeveynlerinin yerini alır.

mutasyon

Son olarak, özelliklerin rekombinasyonunu gerçekleştiririz.

 private void mutation(List<T> population) { for (int i = 0; i < population.size(); i++) { if (random() < mutationProbability) { population.set(i, mutation.apply(population.get(i))); } } }

Önceden tanımlanmış olasılık mutationProbability ile kromozomlar üzerinde “mutasyon” gerçekleştiririz. Mutasyonun kendisi mutation tarafından tanımlanır.

Probleme Özgü Algoritma Yapılandırması

Şimdi, genel uygulamamıza ne tür probleme özgü parametreler sağlamamız gerektiğine bir göz atalım.

 private BiFunction<T, T, T> crossover; private double crossoverProbability; private ToDoubleFunction<T> fitness; private Function<T, T> mutation; private double mutationProbability; private int populationSize = 100; private Supplier<T> supplier; private Predicate<Collection<T>> termination;

Parametreler sırasıyla:

1. çaprazlama operatörü
2. çaprazlama olasılığı
3. Fitness fonksiyonu
4. mutasyon operatörü
5. mutasyon olasılığı
6. Nüfusun büyüklüğü
7. İlk popülasyon için kromozom tedarikçisi
8. sonlandırma işlevi

İşte sorunumuzun yapılandırması:

 new GeneticAlgorithm<char[]>() .setCrossover(this::crossover) .setCrossoverProbability(0.25) .setFitness(this::fitness) .setMutation(this::mutation) .setMutationProbability(0.05) .setPopulationSize(100) .setSupplier(() -> supplier(expected.length)) .setTermination(this::termination) .find()

Çapraz Operatör ve Olasılık

 private char[] crossover(char[] value1, char[] value2) { final int i = (int) round(random() * value1.length); final char[] result = new char(value1.length); System.arraycopy(value1, 0, result, 0, i); System.arraycopy(value2, i, result, i, value2.length - i); return result; }

Çaprazlama olasılığı 0.25'tir, bu nedenle kromozomların ortalama yüzde 25'inin çaprazlama için seçilmesini bekliyoruz. Bir çift kromozomun çaprazlanması için basit bir prosedür uyguluyoruz. Uzunluğun bir kromozomun length olduğu [0..length] aralığından rastgele bir sayı n üretiyoruz. Şimdi bir kromozomdan ilk n karakteri ve ikinciden sonra kalan karakterleri alarak seçilen çifti eşleştiriyoruz.

Fitness fonksiyonu

 private double fitness(char[] value) { return range(0, value.length) .filter(i -> value[i] == expected[i]) .count(); }

Uygunluk işlevi, hedef ifade ile verilen kromozom arasındaki eşleşmelerin sayısını basitçe sayar.

Mutasyon Operatörü ve Olasılık

 private char[] mutation(char[] value) { final char[] result = Arrays.copyOf(value, value.length); for (int i = 0; i < 2; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); int location = (int) round(random() * (value.length - 1)); result[location] = ALPHABET[letter]; } return result; }

Mutasyon işlemi her kromozom üzerinde bağımsız olarak gerçekleştirilir. Mutasyon olasılığı 0,05'tir, bu nedenle popülasyonun ortalama yüzde beşinin mutasyona uğramasını bekliyoruz. Rastgele bir harf konumu seçerek ve değerini alfabeden rastgele bir harfle değiştirerek mutasyona uğrarız. Mutasyona uğramış her kromozom için iki kez yapıyoruz.

Tedarikçi

 private char[] supplier(int length) { final char[] result = new char(length); for (int i = 0; i < length; i++) { int letter = (int) round(random() * (ALPHABET.length - 1)); result[i] = ALPHABET[letter]; } return result; }

Tedarikçi, alfabeden rastgele harfler alarak rastgele ifadeler üretir. Her cümlenin önceden tanımlanmış sabit bir uzunluğu vardır.

Sonlandırma İşlevi

 private boolean termination(Collection<char[]> chars) { count++; final Optional<char[]> result = chars.stream() .filter(value -> round(fitness(value)) == expected.length) .findAny(); if (result.isPresent()) { System.out.println("Count: " + count); System.out.println(result.get()); return true; } final boolean terminated = count == 3000; if (terminated) { chars.forEach(System.out::println); } return terminated; }

Sonlandırma işlevi, çağrıların sayısını sayar ve tam bir eşleşme varsa veya üretim sayısı 3.000'e ulaşırsa true değerini döndürür.

Uygulamak

Artık algoritmamızı test etmeye hazırız. Birkaç kez çalıştırırsanız, tüm çalıştırmaların başarılı olmadığını fark edeceksiniz. Her seferinde, yineleme sayısı farklı olacaktır. Bu, algoritmanın olasılıklı doğasından kaynaklanmaktadır. Algoritmanın geliştirilebileceği birkaç noktası vardır. Çaprazlama ve mutasyon olasılıkları ile oynayabilirsiniz.

Sayıyı düşürmek, kararlı ancak yavaş bir çözüme yol açacaktır. Daha az sayıda kromozom, genetik operatörlerden etkilenecek ve bu nedenle çözüm için daha fazla yineleme gerekli olacaktır.

Sayıları artırmak algoritmayı hızlandıracak, ancak aynı zamanda çözümü kararsız hale getirecektir. Uygun kromozomlar sadece korunmakla kalmayacak, aynı zamanda genetik operatörlerden de etkilenecektir. Bu nedenle “iyi” genlerini kaybederler.

İyi bir denge bulmak önemlidir. Yineleme sayısını artırmak, algoritmaya bir çözüm bulmak için daha fazla fırsat verecek, ancak diğer yandan daha fazla zaman alacaktır. Farklı çaprazlama ve mutasyon yöntemlerini de uygulayabilirsiniz. Bu operatörlerin iyi bir seçimi, çözümün kalitesini büyük ölçüde artıracaktır.

Sıradaki ne?

Burada buzdağının sadece görünen kısmını kapattık. Sadece bir girişi olan bir örnek aldık ve girdi kolayca bir kromozom olarak sunulabilir. Genetik operatörler sade ve basittir.

Gerçek dünya problemini alıp ona genetik algoritmayı uygulamak çok ilginç. Gerçek girdi verilerinin kodlanmasında farklı yaklaşımların yanı sıra farklı çaprazlama ve mutasyon uygulamaları keşfedeceksiniz.

Bir problem, bir metriği optimize etmek için tahmin etmemiz gereken bir dizi parametre aracılığıyla ifade edilebiliyorsa, onu çözmek için kullanabileceğimiz bir GA'yı hızlı bir şekilde kurabiliriz.

En ilginç problemlerden biri yapay sinir ağlarının öğretilmesidir. Optimize edilebilir parametreleri sinaps güçleri olarak ve uygunluk metriğini sinir ağımızın doğru cevabı verdiği girdilerin yüzdesi olarak ayarlayabiliriz. Ondan sonra arkamıza yaslanıp sinir ağımızın arzu ettiğimiz ideal çözüme dönüşmesine izin verebiliriz. Ya da en azından yeterince iyi bir şey elde edene kadar, çünkü evrim zaman alır.