"नमस्ते दुनिया!" आनुवंशिक एल्गोरिदम के साथ

आजकल, आनुवंशिक एल्गोरिदम लोकप्रियता प्राप्त कर रहे हैं। उनका उपयोग विभिन्न प्रकार की समस्याओं को हल करने के लिए किया जाता है। कहीं वे दूसरों की तुलना में अधिक कुशलता से काम करते हैं, कहीं प्रोग्रामर ने सिर्फ दिखाने का फैसला किया ...



तो एक आनुवंशिक एल्गोरिथ्म क्या है? विकिपीडिया के अनुसार, आनुवंशिक एल्गोरिथ्म एक हेयोरिस्टिक खोज एल्गोरिथ्म है जिसका उपयोग अनुकूलन और मॉडलिंग की समस्याओं को बेतरतीब ढंग से चयन करने, संयोजन करने और वांछित मापदंडों को अलग-अलग करने के लिए किया जाता है, जो कि जैविक विकास की याद दिलाता है। यह एक प्रकार की विकासवादी संगणना है। आनुवंशिक एल्गोरिथ्म की एक विशिष्ट विशेषता "क्रॉसिंग" ऑपरेटर के उपयोग पर जोर है, जो उम्मीदवार समाधानों के पुनर्संयोजन का संचालन करता है, जिसकी भूमिका वन्य जीवन में पार करने की भूमिका के समान है।



यानी आनुवंशिक एल्गोरिथ्म हमारे विकास की तरह काम करता है। सबसे पहले, शुरुआती आबादी बनाई जाती है, फिर वे इंटरब्रिड (उत्परिवर्तन संभव हैं)। प्राकृतिक चयन की प्रक्रिया में जीवित आबादी को निर्दिष्ट मानदंडों के अनुपालन के लिए परीक्षण किया जाता है। यदि वे संतुष्ट हैं, तो हर कोई खुश है, यदि नहीं, तो वे अंतिम जीत तक फिर से पार करते हैं।



यह सब कैसे दिखता है आप निम्न आकृति में देख सकते हैं:









एक उदाहरण के रूप में, मैं एक एल्गोरिथ्म देता हूं जो स्ट्रिंग को "हैलो वर्ल्ड!" बनाता है।



इस आनुवंशिक एल्गोरिथ्म में निम्नलिखित पैरामीटर हैं:

जनसंख्या का आकार:	2048
म्यूटेशन (%):	25
परोपकारिता (%):	10

स्रोत कोड

 # इकलौता <iostream> // cout के लिए, आदि।
 वेक्टर क्लास के लिए #include <वेक्टर> //
 #include <string> // string class के लिए
 #include <एल्गोरिथम> सॉर्टिंग एल्गोरिदम के लिए
 यादृच्छिक चर के लिए #include <time.h> //
 #include <math.h> // एब्स के लिए ()

 #define GA_POPSIZE 2048 // जनसंख्या का आकार
 #define GA_MAXITER 16384 // पुनरावृत्तियों की अधिकतम संख्या
 #define GA_ELITRATE 0.10f // Elitism
 #define GA_MUTATIONRATE 0.25f // म्यूटेशन
 #define GA_MUTATION RAND_MAX * GA_MUTATIONRATE
 #define GA_TARGET std :: string ("हैलो वर्ल्ड!")

 नाम स्थान std का उपयोग करना;				

 संरचना ga_struct 
 {
	 स्ट्रिंग str;  // स्ट्रिंग
	 अहस्ताक्षरित इंट फिटनेस;  // उपयुक्तता
 };

 टाइपडिफ वेक्टर <ga_struct> ga_vector;  // कम के लिए

 शून्य init_population (Ga_vector और जनसंख्या,
					  गा_वेक्टर और बफर) 
 {
	 int tsize = GA_TARGET.size ();

	 for (int i = 0; मैं <GA_POPSIZE; i ++) {
		 ga_struct नागरिक;
		
		 नागरिकता। साक्षी = ०;
		 Cit.str.erase ();

		 for (int j = 0; j <tsize; j ++)
			 Cit.str + = (rand ()% 90) + 32;

		 आबादी। पश_बैक (नागरिक);
	 }

	 बफर.सेरीज़ (GA_POPSIZE);
 }

 शून्य calc_fitness (Ga_vector और जनसंख्या)
 {
	 स्ट्रिंग लक्ष्य = GA_TARGET;
	 int tsize = target.size ();
	 अहस्ताक्षरित इंट फिटनेस;

	 for (int i = 0; मैं <GA_POPSIZE; i ++) {
		 फिटनेस = 0;
		 for (int j = 0; j <tsize; j ++) {
			 फिटनेस + = एब्स (इंट (जनसंख्या [i] .str [j] - लक्ष्य [j]));
		 }
		
		 आबादी [i]। गवाह = फिटनेस;
	 }
 }

 बूल fitness_sort (ga_struct x, ga_struct y) 
 {वापसी (x.fitness <y.fitness);  }

 इनलाइन शून्य sort_by_fitness (Ga_vector और जनसंख्या)
 {क्रमबद्ध (जनसंख्या.बीजिन) (, जनसंख्या.एंड), फिटनेस_सोर्ट);  }

 शून्य अभिजात्य (Ga_vector और जनसंख्या, 
				 Ga_vector और बफर, int esize)
 {
	 for (int i = 0; मैं <esize? i ++) {
		 बफ़र [i] .str = जनसंख्या [i] .str;
		 बफर [i]। गवाह = जनसंख्या [i]। गवाह;
	 }
 }

 शून्य उत्परिवर्ती (Ga_struct और सदस्य)
 {
	 int tsize = GA_TARGET.size ();
	 int ipos = rand ()% tsize;
	 int delta = (rand ()% 90) + 32; 

	 member.str [ipos] = ((member.str [ipos] + delta)% 122);
 }

 शून्य दोस्त (Ga_vector और जनसंख्या, ga_vector और बफर)
 {
	 int esize = GA_POPSIZE * GA_ELITRATE;
	 int tsize = GA_TARGET.size (), spos, i1, i2;

	 अभिजात्य (जनसंख्या, बफर, एसाइज़);

	 // आराम करें
	 for (int i = esize; मैं <GA_POPSIZE; i ++) {
		 i1 = रैंड ()% (GA_POPSIZE / 2);
		 i2 = रैंड ()% (GA_POPSIZE / 2);
		 spos = rand ()% tsize;

		 बफर [i] .str = जनसंख्या [i1] .str.substr (0, spos) + 
			             जनसंख्या [i2] .str.substr (spos, esize - spos);

		 अगर (रैंड) (<GA_MUTATION) म्यूटेट (बफर [i]);
	 }
 }

 इनलाइन शून्य Print_best (ga_vector & gav)
 {cout << "सर्वश्रेष्ठ:" << gav [0] .str << "(" << gav [0] .fitness << ")" << endl;  }

 इनलाइन शून्य स्वैप (ga_vector * और जनसंख्या,
				  ga_vector * और बफर)
 {ga_vector * अस्थायी = जनसंख्या;  आबादी = बफर;  बफर = अस्थायी;  }

 int main ()
 {
	 सरंड (अहस्ताक्षरित (समय (NULL)));

	 ga_vector pop_alpha, pop_beta;
	 ga_vector * जनसंख्या, * बफर;

	 init_population (pop_alpha, pop_beta);
	 आबादी = & pop_alpha;
	 बफर = & pop_beta;

	 for (int i = 0; मैं <GA_MAXITER; i ++) {
		 calc_fitness (* जनसंख्या);  // उपयुक्तता की गणना करें
		 Sort_by_fitness (* जनसंख्या);  // जनसंख्या छाँटें
		 Print_best (* जनसंख्या);  // सबसे अच्छी आबादी प्रिंट

		 अगर (* जनसंख्या) [0]। गवाह == 0) विराम;

		 दोस्त (* जनसंख्या, * बफर);  // मेट आबादी
		 स्वैप (जनसंख्या, बफर);  // बफ़र्स साफ़ करें
	 }

	 वापसी 0;
 }

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



उपयुक्तता का निर्धारण

आइए एक आबादी की उपयुक्तता का निर्धारण करने के कार्य पर एक नज़र डालें:

void calc_fitness(ga_vector &population)

{

string target = GA_TARGET;

int tsize = target.size();

unsigned int fitness;



for (int i=0; i<GA_POPSIZE; i++) {

fitness = 0;

for (int j=0; j<tsize; j++) {

fitness += abs(int(population[i].str[j] - target[j]));

}



population[i].fitness = fitness;

}

}









सिद्धांत रूप में, आबादी के प्रत्येक सदस्य को यहां स्कैन किया जाता है और लक्ष्य रेखा में उसके साथ तुलना की जाती है। प्रतीकों के बीच के अंतर को जोड़ा जाता है और संचित राशि को फिटनेस मूल्य के रूप में उपयोग किया जाता है (इस प्रकार, यह जितना छोटा होता है, उतना अच्छा)।



परिणाम

जब निष्पादित किया जाता है, तो कार्यक्रम सबसे अच्छी आबादी और इसकी उपयुक्तता (कोष्ठक में संख्या) प्रदर्शित करता है।

Best: IQQte=Ygqem# (152)

Best: Crmt`!qrya+6 (148)

Best: 8ufxp+Rigfm* (140)

Best: b`hpf"woljh[ (120)

Best: b`hpf"woljh4 (81)

Best: b`hpf"woljh" (63)

Best: Kdoit!wnsk_! (24)

Best: Kdoit!wnsk_! (24)

Best: Idoit!wnsk_! (22)

Best: Idoit!wnsk_! (22)

Best: Idoit!wnsk_! (22)

Best: Idoit!wnsk_! (22)

Best: Ifknm!vkrlf? (17)

Best: Ifknm!vkrlf? (17)

Best: Gfnio!wnskd$ (14)

Best: Ffnjo!wnskd$ (14)

Best: Hflio!wnskd$ (11)

Best: Hflio!wnskd$ (11)

Best: Kflkn wosld" (8)

Best: Ifmmo workd" (6)

Best: Hfljo wosld" (5)

Best: Hflmo workd" (4)

Best: Hflmo workd" (4)

Best: Hflmo workd" (4)

Best: Iflmo world! (3)

Best: Iflmo world! (3)

Best: Hflmo world! (2)

Best: Hflmo world! (2)

Best: Hflko world! (2)

Best: Hflko world! (2)

Best: Hdllo world! (1)

Best: Hfllo world! (1)

Best: Hfllo world! (1)

Best: Helko world! (1)

Best: Hfllo world! (1)

Best: Hfllo world! (1)

Best: Hfllo world! (1)

Best: Hello world! (0)









निष्कर्ष

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



आवेदन उदाहरण

मापदंडों की एक सीमा पर एक ट्रेडिंग रोबोट का परीक्षण करने के लिए, आप "चक्र के माध्यम से नहीं" (अब सभी कार्यक्रमों में) रेंज कर सकते हैं, लेकिन आनुवंशिक एल्गोरिदम का उपयोग कर सकते हैं। और समय 9-12 गुना कम हो जाता है। #



मूल लेख अंग्रेजी में।

आनुवंशिक एल्गोरिथ्म क्या है?