आनुवंशिक एल्गोरिथम। सिद्धांत से अभ्यास तक

शुभ दोपहर हाल ही में, मैंने आत्म-शिक्षा करने का फैसला किया। यह आनुवंशिक एल्गोरिदम के साथ शुरू करने का निर्णय लिया गया था।

जीए के उल्लेखनीय गुणों में से एक यह है कि चयन, क्रॉसिंग और म्यूटेशन प्रक्रियाओं का व्यक्तियों में जनरेशन के बारे में कोई पता नहीं है - उनके लिए यह केवल 0 और 1. एकमात्र फ़ंक्शन है जो जानता है कि ये 0 और 1 हैं - यह एक फिटनेस फंक्शन है।

इसलिए, मैंने फैसला किया कि किसी भी GA के लिए वायरफ्रेम क्लास लिखना अच्छा होगा। यह इस लेख के बारे में क्या होगा। यह माना जाता है कि आप पहले से ही आनुवंशिक एल्गोरिदम की मूल बातें से परिचित हैं।

यह किसके लिए दिलचस्प है, मैं बिल्ली के नीचे पूछता हूं।


कोड जावा में लिखा जाएगा।

इस तथ्य के बावजूद कि हम वायरफ्रेम लिख रहे हैं, हमें इसका परीक्षण करने की आवश्यकता है। इसके लिए, मैंने क्लासिक एनपी-पूर्ण समस्या - यात्रा विक्रेता समस्या को लिया।

अनुप्रयोग वास्तुकला के बारे में थोड़ा सा:

जीनोम (व्यक्तिगत) का प्रतिनिधित्व करने के लिए हम लंबे [] का उपयोग करेंगे। किसी कारण से, यह विकल्प मुझे बूलियन [] से बेहतर लग रहा था।

हमें एक इंटरफ़ेस भी चाहिए:

public interface FitnessFunction { int getArity(); //-    long run(long[] genom); //    . } 

हम जिस वर्ग का विकास कर रहे हैं:

 public class GeneticEngine{ public GeneticEngine(FitnessFunction fitnessFunction) {...} // public long[] run() {...} //  private void generateFirstGeneration() {...} //   private void selection(){...} //  private void crossing() {...} //  private void mutation() {...} //  } 

चूंकि हम एक "सार्वभौमिक" वर्ग लिख रहे हैं, इसलिए यह आवश्यक है कि यह क्रॉसब्रैडिंग और चयन के विभिन्न प्रकारों का समर्थन करता है, इसलिए 2 एनम जोड़े गए (Enum):

 public enum SelectionType { TOURNEY, ROULETTE_WHEEL } public enum CrossingType { ONE_POINT_RECOMBINATION, TWO_POINT_RECOMBINATION, ELEMENTWISE_RECOMBINATION, ONE_ELEMENT_EXCHANGE } 

... और कुछ निजी क्षेत्र:

 private int genomLength; //    private long generationCount; //-  private int individualCount; //- (,)   private SelectionType selectionType; //  private CrossingType crossingType; //  private boolean useMutation; //  private double mutationPercent; //    

उनके लिए सेटर और गेटर्स हैं।

और अब, पहली चीजें पहले ...

पहली पीढ़ी की पीढ़ी।

सब कुछ बहुत सरल है: हम यादृच्छिक द्वारा लोंग उत्पन्न करते हैं, हम लोंगो से जीनोम की रचना करते हैं और उन्हें एक सरणी में रखते हैं। मैं कोड नहीं दूंगा।

चयन।

मुझे 2 प्रकार के चयन मिले:

• रूले का पहिया
• टूर्नामेंट

चयन प्रक्रिया जीनोम की एक नई सरणी बनाती है।

 private void selection(){ switch (selectionType) { case ROULETTE_WHEEL:{ float[] wheel = new float[this.individualCount]; wheel[0] = //   1-  for (int i=1;i<this.individualCount;i++){ wheel[i] = wheel[i-1] + //   i-  } float all = wheel[this.individualCount-1]; for (int i=0;i<this.individualCount;i++){ float index = Math.abs(this.random.nextFloat())*all; int l = 0; int r = individualCount-1; int c = 0; while (l < r){ c = (l+r) >> 1; if (index <= while[c]){ r = c; }else{ l = c + 1; } } this.genomListOffsprings[i] = this.genomListParents[l].clone(); } break; } case TOURNEY:{ for (int i=0;i<this.individualCount;i++){ int index1 = random.nextInt(individualCount); int index2 = random.nextInt(individualCount); long fr1 = //   index1  long fr2 = //   index2  this.genomListOffsprings[i] = fr1 > fr2 ? this.genomListParents[index1].clone() : this.genomListParents[index2].clone(); } break; } } 

कुछ टिप्पणियाँ "अपने दम पर":

• परीक्षणों के दौरान, यह पता चला कि अधिकांश प्रदर्शन फिटनेस फ़ंक्शन (लगभग 90% समय)।
• प्रत्येक पीढ़ी पर कार्यों के परिणामों के कैशिंग का उपयोग करते हुए, पूरे एल्गोरिथ्म के प्रदर्शन को 3-4 गुना बढ़ाना संभव था।
• पूर्ववर्ती दो बिंदुओं के कारण, रूले टूर्नामेंट की तुलना में बहुत खराब एल्गोरिदम निकला।

अंतर प्रजनन।

क्रॉसिंग होता है:

• एकल बिंदु पुनर्संयोजन।
• बिंदु से बिंदु पुनर्संयोजन।
• तात्विक पारगमन।
• एक ही जीन साझा करना।

कुछ टिप्पणियाँ "अपने दम पर":

• परीक्षणों के दौरान, यह पता चला कि तत्व-वार क्रॉसब्रेडिंग सबसे अच्छा काम करता है। जबकि शेष 3 एल्गोरिदम में एक ही "उपयोगिता" है।
• (स्पष्ट) एक जीन का आदान-प्रदान O (1) के लिए काम करता है, बाकी एल्गोरिदम O (L) के लिए काम करते हैं, जहां l जीनोम की लंबाई है।
• पिछले पैराग्राफ के बावजूद, सभी 4 एल्गोरिदम लगभग एक ही समय (अर्थात् समय) में काम करते हैं। अधिक सटीक: संपूर्ण जीए के ऑपरेटिंग समय में फिटनेस फ़ंक्शन 90% पर है, इसकी पृष्ठभूमि के विपरीत, O (1) और O (L) क्रॉसिंग के लिए बराबर हैं।
• पिछले तीन बिंदुओं के आधार पर, मैं समझता हूं (मेरा मानना ​​है) तत्व-क्रॉसिंग सबसे अच्छा क्रॉसिंग एल्गोरिदम है।

* क्रॉसिंग और म्यूटेशन के कार्य के लिए, मैंने बाइनरी ऑपरेशन का उपयोग किया। इसलिए, हमें कई स्थिर चर घोषित करने पड़े।

 public static final int OCTET_LENGTH = 64; // -    public static final int MASK_FOR_MOD = OCTET_LENGTH - 1; //  "x%64"   "x & MASK_FOR_MOD" public static final int SHIFT_FOR_DIVISION; //  "x/64" - "x >> SHIFT_FOR_DIVISION" 

दो जीनोम को पार करने का कार्य:
(दिखाया गया कोड केवल बिटवाइज़ क्रॉसिंग के लिए है)

 private void cross(long[] genom1, long[] genom2) { switch (crossingType) { ... case ELEMENTWISE_RECOMBINATION:{ for (int outerOffset = 0; outerOffset < this.sizeOfArray; outerOffset++) { long mask = this.random.nextLong(); //   ,    (1- , 0-) long swapMask = (genom1[outerOffset] ^ genom2[outerOffset]) & mask; genom1[outerOffset] ^= swapMask; genom2[outerOffset] ^= swapMask; } break; } } 

स्पष्टीकरण:
एक दूसरे के साथ संख्याओं और बी का आदान-प्रदान करने के लिए, आपको यह करना होगा:
swapMask = एक xor b;
a = a xor swapMask;
b = b xor स्वैपमैप;

और अगर हम स्वैपमैप पर मास्क (और) लगाते हैं, तो a और b केवल उन बिट्स को बदलेंगे जो मास्क नंबर में == 1 हैं।

swapMask = (a xor b) और मास्क;
a = a xor swapMask;
b = b xor स्वैपमैप;

उत्परिवर्तन।

 private void mutation() { for (long[] genom : this.genomListOffsprings) { if (random.nextDouble() <= mutationPercent) { mutate(genom); } } } private void mutate(long[] genom) { int index = this.random.nextInt(this.genomLength); int outerOffset = index >> SHIFT_FOR_DIVISION; int innerOffset = (index & MASK_FOR_MOD); long mask = 1L << innerOffset; genom[outerOffset] ^= mask; } 

थोड़ा उल्टा करने के लिए, आपको चाहिए:
bit = bit xor 1;
इसलिए, किसी भी संख्या में किसी भी बिट को पलटने के लिए, इकाई को वांछित स्थिति में स्थानांतरित करना आवश्यक है।

"शरीर।"

और मुख्य कार्य जो पिछले सभी को जोड़ता है:

 public long[] run() { generateFirstGeneration(); while (currentGeneration < generationCount) { selection(); this.crossing(); if (useMutation) { mutation(); } currentGeneration++; } return . } 

आवेदन।

इसका उपयोग करना काफी सरल है:
सबसे पहले आपको फिटनेसफंक्शन क्लास का वर्णन करना होगा।
और फिर ...

 MyFitnessFunction ff = new MyFitnessFunction(); GeneticEngine ge = new GeneticEngine(ff); ge.setIndividualCount(1000); // -    ge.setGenerationCount(10000); // -  ge.setSelectionType(SelectionType.TOURNEY); //  ge.setCrossingType(CrossingType.ELEMENTWISE_RECOMBINATION); //  ge.setUseMutation(true); //    ge.setMutationPercent(0.02d); //    long[] better = ge.run(); // 

यात्रा विक्रेता समस्या पर वापस आते हैं।

चूंकि शहरों के बीच की दूरी random.nextInt (256) से भरी हुई थी। मैंने यह सुझाव देने का साहस किया कि 2 शहरों के बीच की औसत दूरी = 128. => सभी शहरों के लिए मार्ग की औसत लंबाई = 128 * 256 = 32768। (! मैं गलत हो सकता है)।

पर

 IndividualCount = 100; GenerationCount = 10000; SelectionType = SelectionType; CrossingType = ELEMENTWISE_RECOMBINATION; UseMutation = true; MutationPercent = 0.02d; 

GA 6-7 सेकंड के लिए पथ = 10000-12000 पाता है। जो औसत से 3 गुना बेहतर है।

पर

 IndividualCount = 1000; GenerationCount = 10000; 

5500-7000 प्रति मिनट।

पर

 IndividualCount = 10000; GenerationCount = 100000; 

कोड लगभग 15 घंटे तक चलता है। और मार्ग = 3500-4000 पाता है।

आगे कहां बढ़ेंगे।

• मुझे उम्मीद है कि जानकार लोग आपको बताएंगे कि रूले को कैसे लागू किया जाए।
• आप पीए की पीढ़ियों की संख्या के अनुसार नहीं रोक सकते हैं, लेकिन फिटनेस फ़ंक्शन के कुछ मूल्य तक पहुंचने के बाद, या जब पीढ़ियों के फिटनेस फ़ंक्शन के औसत मूल्यों में अंतर छोटा हो गया है।
• आप सभी पीढ़ियों के लिए सर्वश्रेष्ठ फिटनेस फ़ंक्शन के साथ एक व्यक्ति को स्टोर कर सकते हैं। या सभी पीढ़ियों के लिए नहीं, लेकिन केवल उन व्यक्तियों से जिनके लिए फिटनेस फ़ंक्शन की गणना की गई थी - यह महंगा नहीं होगा।

GitHub से लिंक करें। मुझे खुशी होगी अगर कोई काम आएगा।

UPD: कोड जावा में लिखा गया है, लेकिन मैंने इसे java.util का उपयोग किए बिना लिखने की कोशिश की, और इसलिए यह C की तरह लग रहा था।
इस पहलू का कारण क्या है:

• डेटा संग्रहीत करते समय कोई ओवरहेड नहीं होगा।
• C / C ++ / php / किसी भी C- जैसी भाषा में कोड आसानी से पोर्टेबल हो जाता है।
• यह प्रदर्शन को चोट नहीं पहुंचाएगा (शायद थोड़ी वृद्धि भी)।
• कोड को पढ़ना अधिक मुश्किल नहीं होगा।

(टिप्पणियों में, कोड एस-शनी के साथ भ्रमित था, इसलिए मैं इस कार्य को पूरा करने पर विचार करता हूं)

UPD2: लियोकार्ड को रूले (बाइनरी खोज में) में एक त्रुटि मिली। फिक्स्ड।