ग्लोबल एक्सट्रैमा खोजने के लिए पायथन आनुवंशिक एल्गोरिथ्म

पृष्ठभूमि

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



और इसलिए मैंने एल्गोरिथ्म के एक दृश्य के साथ पायथन में अपने छोटे पैकेज को लिखने का फैसला किया, जिसके अनुसार इस एल्गोरिथ्म को कॉन्फ़िगर करना और चयनित मॉडल की सूक्ष्मताओं की तलाश करना सुविधाजनक होगा।

इस छोटे से लेख में, मैं इस प्रक्रिया, टिप्पणियों और परिणामों को साझा करना चाहूंगा।

एल्गोरिथ्म का सिद्धांत

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

फिलहाल, पैकेज केवल एक जीए को लागू करता है, जो कि इनपुट डेटा द्वारा एक साधारण गुहा के माध्यम से परिचालित किया जाता है। मैं आपको कुछ चुनिंदा जेनेटिक फ़ंक्शंस और बेसिक एल्गोरिथम सॉल्यूशंस के बारे में बताऊंगा।

मोनोक्रोमोसोमल व्यक्ति अपने प्रत्येक जीन में संबंधित एक्स या वाई समन्वय के बारे में जानकारी देता है। एक आबादी कई व्यक्तियों द्वारा निर्धारित की जाती है, लेकिन जनसंख्या को 4 व्यक्तियों में विभाजित किया जाता है। यह समाधान, निश्चित रूप से, एक स्थानीय इष्टतम के अभिसरण से बचने के प्रयास के कारण है, क्योंकि कार्य एक वैश्विक चरम को खोजने के लिए है। ऐसा विभाजन, जैसा कि अभ्यास ने दिखाया है, कई मामलों में पूरी आबादी में एक जीनोटाइप को हावी होने की अनुमति नहीं देता है, लेकिन, इसके विपरीत, "विकास" को अधिक गतिशीलता देता है। आबादी के ऐसे प्रत्येक भाग के लिए, निम्नलिखित एल्गोरिथ्म लागू किया जाता है:

1. चयन रैंकिंग विधि के समान होता है। 3 व्यक्तियों को सर्वश्रेष्ठ फिटनेस फ़ंक्शन संकेतक के साथ चुना जाता है (यानी, व्यक्तियों को उपयोगकर्ता द्वारा निर्धारित फ़ंक्शन के आरोही / अवरोही क्रम में क्रमबद्ध किया जाता है, जो अनुकूलन फ़ंक्शन के रूप में कार्य करता है)।
2. इसके बाद, क्रॉसिंग फ़ंक्शन को इस तरह से लागू किया जाता है कि एक नई पीढ़ी (या 4 व्यक्तियों की आबादी का एक नया खंड) फिटनेस फ़ंक्शन के बेहतर संकेत और दो अन्य व्यक्तियों से उत्परिवर्तित जीन की एक जोड़ी के साथ एक व्यक्ति से 2 जोड़ी अनमैटेड जीन प्राप्त करता है। म्यूटेशन फ़ंक्शन के संकलन पर अधिक अगले भाग में लिखा जाएगा।

चयन के संचालन का सिद्धांत, क्रॉसब्रेजिंग और म्यूटेशन नेत्रहीन इस तरह दिखता है (पीढ़ी एन में, व्यक्तियों के गुणसूत्र पहले से ही सही क्रम में सॉर्ट किए जाते हैं, और एक छोटे से काले वर्ग का अर्थ है उत्परिवर्तन):

प्राथमिक परीक्षण और अवलोकन

तो, हम इस एल्गोरिथ्म को दो सरल उदाहरणों पर परखते हैं:

टेस्ट 1

$$

$$f(x, y) = sin(x) + cos(y)$$

परीक्षण २

$$

$$\frac{4 \sqrt{x} - 5y }{ 3x ^ 2 + 2 y ^ 2 - 2 x + 1}$$

एल्गोरिथ्म के संचालन को टकटकी और यादृच्छिक पोकिंग के परीक्षण और अध्ययन के बाद, कई परिकल्पना-प्रतिमान सामने आए:

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

  $$

  $$[-1, 1)$$
  जिसके कारण व्यक्ति चरम सीमा के आसपास के क्षेत्र में नहीं रह सकते हैं और विभिन्न पीढ़ियों के व्यक्तियों के बीच की दूरी में अपेक्षाकृत तेज उतार-चढ़ाव होता है। कुछ मामलों में, इस तरह के दोलन एक स्थानीय चरम सीमा से बाहर निकलने के लिए उपयोगी हो सकते हैं, उदाहरण के लिए, एक आवधिक कार्य, लेकिन एक दूसरे से एक्स्ट्रेमा एक महान दूरी पर हो सकता है (यूक्लिडियन अर्थ में दूरी)
• कई मामलों में, चरम बिंदु 5-15 पीढ़ियों में व्यक्तियों द्वारा पहुंच जाता है, और शेष पीढ़ियों ने इस चरम सीमा के आसपास "बेकार" छलांग लगाई
• शून्य पीढ़ी केवल एक वर्ग में यादृच्छिक संख्याओं से भरी होती है

  $$

  $$[-1, 1)*[-1, 1)$$
  
  और ऐसे मामले हो सकते हैं जब यह वर्ग एक स्थानीय चरम सीमा को कवर करता है, जो हमें शोभा नहीं देता

प्रपत्र के कई एक्स्ट्रेमा के साथ एक सतह पर विचार करें:

$$

$$g(x, y) = \sum\limits_{i=1}^nf_n(h, x_0, y_0), f(h, x_0, y_0) = h*exp(-(x - x_0)^2 - (y - y_0)^2)$$

फंक्शन g की एक्स्रेमा बिंदुओं पर होगी

$$

$$(x_0, y_0)$$

।

परीक्षण ३

$$

$$g(x, y) = f_1(2, 0, 0) + f_2(5, 3, 3)$$

$$

$$g(x, y) = 2exp(-x^2 - y^2) + 5exp(-(x - 3)^2 - (y - 3)^2)$$

यह उदाहरण उपरोक्त सभी टिप्पणियों की पुष्टि करता है और दिखाता है।

आनुवंशिक एल्गोरिथम अपग्रेड

तो, इस समय, म्यूटेशन फ़ंक्शन को बहुत ही प्राथमिक रूप से बनाया गया है: यह आधे-अंतराल से यादृच्छिक मान जोड़ता है

$$

$$[-1, 1)$$

उत्परिवर्तित जीन को। इस तरह के उत्परिवर्तन आक्रमण कभी-कभी एल्गोरिथ्म के सही संचालन में हस्तक्षेप करते हैं, लेकिन इस दोष को ठीक करने का एक प्रभावी तरीका है।

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

परीक्षण १

$$

$$f(x, y) = sinx$$

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

लेकिन स्थानीय चरम सीमाओं की समस्या के बारे में क्या? एक परिचित उदाहरण पर विचार करें।

परीक्षण २

$$

$$g(x, y) = f_1(2, 0, 0) + f_2(5, 3, 3)$$

$$

$$g(x, y) = 2exp(-x^2 - y^2) + 5exp(-(x - 3)^2 - (y - 3)^2)$$

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

सारांश

मैं परिणाम को संक्षेप में बताता हूं:

• ,
• ,

...

• , . , , aka
• मानक अनुकूलन विधियों के साथ समान एल्गोरिदम की समय और दक्षता में तुलना, उदाहरण के लिए, ढाल वंश
• नई पैकेज सुविधाएँ (संभावना)