🙎🏾 💃🏽 🤠 Optlib। जंग में एक आनुवंशिक अनुकूलन एल्गोरिथ्म का कार्यान्वयन 📣 🤶🏽 🍬

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

वैश्विक अनुकूलन की समस्या

अनुकूलन समस्या आमतौर पर निम्नानुसार तैयार की जाती है।

कुछ दिए गए फ़ंक्शन f ( x ) के लिए, x के सभी संभावित मूल्यों के बीच , एक मान x 'जैसे कि f (x') एक न्यूनतम (या अधिकतम) मान लेता है। इसके अलावा, x विभिन्न सेटों से संबंधित हो सकता है - प्राकृतिक संख्याएँ, वास्तविक संख्याएँ, जटिल संख्याएँ, वैक्टर या मैट्रीस।

फ़ंक्शन f ( x ) के चरम से हमारा मतलब एक बिंदु x है , जिस पर फ़ंक्शन f ( x ) का व्युत्पन्न शून्य के बराबर है।

कई एल्गोरिदम हैं जो फ़ंक्शन के चरम को खोजने की गारंटी देते हैं, जो किसी दिए गए शुरुआती बिंदु x _{0 के} पास एक स्थानीय न्यूनतम या अधिकतम है। इस तरह के एल्गोरिदम में शामिल हैं, उदाहरण के लिए, ढाल वंश एल्गोरिदम। हालांकि, व्यवहार में, किसी फ़ंक्शन के वैश्विक न्यूनतम (या अधिकतम) को खोजने के लिए अक्सर यह आवश्यक होता है कि किसी वैश्विक एक्सट्रीम के अतिरिक्त , एक्स की दी गई सीमा में, कई स्थानीय एक्सट्रैमा होते हैं।

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

सबसे प्रसिद्ध (और लागू करना मुश्किल) एल्गोरिदम में से एक आनुवंशिक एल्गोरिदम है।

आनुवंशिक एल्गोरिथ्म की सामान्य योजना

एक आनुवंशिक एल्गोरिथ्म का विचार धीरे-धीरे पैदा हुआ और 1960 के दशक के उत्तरार्ध में - 1970 के दशक के प्रारंभ में बना। जॉन हॉलैंड की पुस्तक "प्राकृतिक और कृत्रिम प्रणालियों में अनुकूलन" (1975) के विमोचन के बाद आनुवंशिक एल्गोरिदम को एक शक्तिशाली विकास मिला।

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

किसी व्यक्ति को दिए गए बिंदु x के लिए उद्देश्य फ़ंक्शन के मूल्य के साथ संभव मानों के सेट के बीच एक x मान है।
गुणसूत्र - x का मान।
गुणसूत्र - x का मान यदि x एक सदिश है।
फिटनेस फंक्शन (फिटनेस फंक्शन, ऑब्जेक्टिव फंक्शन) अनुकूलित फंक्शन f ( x ) है।
जनसंख्या व्यक्तियों का एक संग्रह है।
पीढ़ी - आनुवंशिक एल्गोरिथ्म के पुनरावृत्तियों की संख्या।

प्रत्येक व्यक्ति सभी संभावित समाधानों के सेट के बीच x के एक मान का प्रतिनिधित्व करता है। अनुकूलित फ़ंक्शन का मान (भविष्य में, संक्षिप्तता के लिए, हम मानते हैं कि हम फ़ंक्शन के न्यूनतम की तलाश कर रहे हैं) की गणना प्रत्येक एक्स के मूल्य के लिए की जाती है। हम मानते हैं कि कम महत्वपूर्ण उद्देश्य उद्देश्य है, बेहतर यह समाधान है।

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

आनुवांशिक एल्गोरिथ्म का संरचनात्मक चित्र निम्नलिखित आकृति में दिखाया गया है:

हम एल्गोरिथ्म के प्रत्येक चरण पर अधिक विस्तार से विचार करते हैं।

एक प्रारंभिक जनसंख्या बनाएं

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

गुणसूत्रों को बेतरतीब ढंग से वितरित करने के बजाय, आप गुणसूत्रों को बना सकते हैं ताकि x के प्रारंभिक मान समान रूप से दिए गए चरण के साथ खोज क्षेत्र में वितरित किए जा सकें, जो इस बात पर निर्भर करता है कि एल्गोरिथ्म के इस चरण में कितने व्यक्ति बनाए जाएंगे।

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

सिद्धांत रूप में, जनसंख्या के आकार को जेनेटिक एल्गोरिदम के पूरे काम में निरंतर नहीं रहना पड़ता है, अक्सर जैसे ही पीढ़ी की संख्या बढ़ती है, जनसंख्या का आकार कम हो सकता है, क्योंकि समय के साथ, व्यक्तियों की बढ़ती संख्या वांछित समाधान के करीब स्थित होगी। हालांकि, अक्सर जनसंख्या का आकार लगभग स्थिर बना रहता है।

क्रॉसब्रीडिंग के लिए व्यक्तियों का चयन

जनसंख्या बनाने के बाद, यह निर्धारित करना आवश्यक है कि कौन से व्यक्ति क्रॉस-ब्रीडिंग ऑपरेशन में भाग लेंगे (अगला पैराग्राफ देखें)। इस चरण के लिए विभिन्न एल्गोरिदम हैं। उनमें से सबसे सरल प्रत्येक के साथ प्रत्येक व्यक्ति को पार करना है, लेकिन फिर अगले चरण में आपको कई क्रॉस-प्रजनन संचालन करना होगा और उद्देश्य फ़ंक्शन के मूल्यों की गणना करना होगा।

अधिक सफल गुणसूत्र (उद्देश्य फ़ंक्शन का न्यूनतम मूल्य के साथ) के साथ संभोग व्यक्तियों के लिए अधिक से अधिक मौका देना बेहतर है, और जिन व्यक्तियों का उद्देश्य फ़ंक्शन अधिक (बदतर) है, वे वंश को छोड़ने की क्षमता से वंचित करना चाहते हैं।

इस प्रकार, इस स्तर पर, आपको व्यक्तियों के जोड़े बनाने की आवश्यकता है (या जरूरी नहीं कि जोड़े यदि अधिक व्यक्ति क्रॉसिंग में भाग ले सकते हैं), जिसके लिए अगले चरण में क्रॉसिंग ऑपरेशन किया जाएगा।

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

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

इस ऑपरेशन का परिणाम क्रॉसिंग के लिए भागीदारों की एक सूची होगी।

चौराहा

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

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

बिटवाइज़ इस तरह से काम करती है कि बेटी गुणसूत्र में एक माता-पिता के बिट्स का हिस्सा होता है और दूसरे माता-पिता के बिट्स का हिस्सा होता है, जैसा कि निम्नलिखित आकृति में दिखाया गया है:

आमतौर पर मूल विभाजन बिंदु को यादृच्छिक रूप से चुना जाता है। ऐसे क्रॉस के साथ दो बच्चे पैदा करना आवश्यक नहीं है, अक्सर उनमें से एक तक सीमित होता है।

यदि मूल गुणसूत्रों का विभाजन बिंदु एक है, तो इस तरह के क्रॉसिंग को एकल-बिंदु कहा जाता है। लेकिन आप बहु-बिंदु विभाजन का भी उपयोग कर सकते हैं, जब मूल गुणसूत्रों को कई वर्गों में विभाजित किया जाता है, जैसा कि निम्नलिखित आकृति में दिखाया गया है:

इस मामले में, बेटी गुणसूत्रों के अधिक संयोजन संभव हैं।

यदि गुणसूत्र फ़्लोटिंग पॉइंट नंबर हैं, तो ऊपर वर्णित सभी विधियों को उन पर लागू किया जा सकता है, लेकिन वे बहुत प्रभावी नहीं होंगे। उदाहरण के लिए, यदि फ्लोटिंग-पॉइंट संख्या बिटवाइज़ पार की जाती है, जैसा कि पहले बताया गया है, तो कई क्रॉसिंग ऑपरेशन बेटी गुणसूत्रों का निर्माण करेंगे जो कि माता-पिता में से एक से केवल दशमलव स्थान में भिन्न होंगे। दोहरी-सटीक फ़्लोटिंग-पॉइंट संख्याओं का उपयोग करते समय स्थिति विशेष रूप से बढ़ जाती है।

इस समस्या को हल करने के लिए, यह याद रखना आवश्यक है कि IEEE 754 मानक के अनुसार फ्लोटिंग पॉइंट नंबरों को तीन पूर्णांक संख्याओं के रूप में संग्रहीत किया जाता है: S (एक बिट), M और N, जिससे फ्लोटिंग पॉइंट संख्या की गणना x = (-1) × के रूप में की जाती है एम × 2 ^एन। फ्लोटिंग-पॉइंट संख्याओं को पार करने का एक तरीका यह है कि संख्या को घटकों में विभाजित करें S, M, N, जो पूर्णांक हैं, और फिर M और N के ऊपर वर्णित बिटवाइज़ क्रॉसिंग ऑपरेशन्स को लागू करते हैं, इनमें से किसी एक के S को चुनें। माता-पिता, और एक बेटी को गुणसूत्र बनाने के लिए प्राप्त मूल्यों से।

कई समस्याओं में, एक व्यक्ति के पास एक नहीं, बल्कि कई गुणसूत्र होते हैं, और यह विभिन्न प्रकारों (पूर्णांक और फ्लोटिंग-पॉइंट नंबर) का भी हो सकता है। फिर ऐसे गुणसूत्रों को पार करने के लिए और भी विकल्प हैं। उदाहरण के लिए, एक बेटी को व्यक्तिगत बनाते समय, आप माता-पिता के सभी गुणसूत्रों को पार कर सकते हैं, या आप बिना परिवर्तन के माता-पिता में से कुछ गुणसूत्रों को पूरी तरह से स्थानांतरित कर सकते हैं।

परिवर्तन

उत्परिवर्तन आनुवंशिक एल्गोरिथ्म का एक महत्वपूर्ण चरण है जो व्यक्तिगत गुणसूत्रों की विविधता का समर्थन करता है और इस तरह उन संभावनाओं को कम करता है जो समाधान जल्दी से एक वैश्विक के बजाय कुछ स्थानीय न्यूनतम में परिवर्तित हो जाएंगे। एक उत्परिवर्तन एक व्यक्ति के गुणसूत्र में एक यादृच्छिक परिवर्तन है जिसे अभी पार करके बनाया गया है।

एक नियम के रूप में, एक उत्परिवर्तन की संभावना बहुत अधिक सेट नहीं की जाती है ताकि उत्परिवर्तन एल्गोरिदम के अभिसरण में हस्तक्षेप न करे, अन्यथा यह सफल गुणसूत्र वाले व्यक्तियों को खराब कर देगा।

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

एक बिट का म्यूटेशन:

कई बिट्स का म्यूटेशन:

एक उत्परिवर्तन के लिए बिट्स की संख्या या तो पूर्वनिर्धारित हो सकती है या एक यादृच्छिक चर हो सकती है।

उत्परिवर्तन के परिणामस्वरूप, व्यक्ति अधिक सफल और कम सफल दोनों हो सकते हैं, लेकिन यह ऑपरेशन शून्य और उन लोगों के सेट के साथ एक सफल गुणसूत्र की अनुमति देता है, जो माता-पिता के व्यक्तियों को गैर-शून्य संभावना के साथ प्रकट नहीं होना था।

चयन

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

चयन एल्गोरिदम भी भिन्न हो सकते हैं। अक्सर, जिन व्यक्तियों के गुणसूत्र किसी समाधान खोज के दिए गए अंतराल के भीतर नहीं आते हैं, उन्हें पहले छोड़ दिया जाता है।

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

एल्गोरिथ्म अंत की स्थिति

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

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

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

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

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

optlib

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

ऑप्टलिब एमआईटी लाइसेंस के तहत वितरित एक खुला स्रोत पुस्तकालय है।

Github पर पेज - https://github.com/Jenyay/rust-optimization
पेज at crates.io - https://crates.io/crates/optlib
प्रलेखन - https://docs.rs/optlib

ऑप्टलिब :: आनुवंशिक

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

ऑप्टलिब :: आनुवंशिक मॉड्यूल को इस तरह से डिज़ाइन किया गया है कि आनुवंशिक एल्गोरिथ्म को "क्यूब्स से" इकट्ठा करना संभव है। संरचना का एक उदाहरण बनाते समय जिसके भीतर आनुवंशिक एल्गोरिथम का कार्य होगा, आपको यह निर्दिष्ट करने की आवश्यकता है कि कौन से एल्गोरिदम का उपयोग आबादी बनाने के लिए किया जाएगा, भागीदारों, क्रॉस, म्यूट, चयन का चयन करें, और एल्गोरिथ्म को बाधित करने के लिए किस मानदंड का उपयोग किया जाता है।

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

पुस्तकालय में, वह मामला जहां गुणसूत्र भिन्नात्मक संख्याओं के एक वेक्टर होते हैं, अर्थात्। जब फ़ंक्शन f ( x ) को छोटा किया जाता है, जहां x फ़्लोटिंग-पॉइंट नंबरों ( f32 या f64 ) का वेक्टर होता है।

ऑप्टलिब :: आनुवंशिक का उपयोग करके अनुकूलन उदाहरण

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

F (b o l d s y m b o l x) = 418.9829 N - s u m_{i = 1}^{N} x_{i} s i n (s q r t | x_{i} |)

$F (\ boldsymbol x) = 418.9829N - \ sum_ {i = 1} ^ {N} x_i \ sin (\ sqrt {| x_i |})$

अंतराल -500 में न्यूनतम Schweffel फ़ंक्शन <= x _i <= 500 बिंदु x ' पर स्थित है, जहां सभी x _i = 420.9687 के लिए i = 1, 2, ..., N, और इस बिंदु पर फ़ंक्शन का मान f ( x' ) है = 0।

यदि N = 2 है, तो इस फ़ंक्शन की त्रि-आयामी छवि इस प्रकार है:

यदि हम इस फ़ंक्शन की स्तर रेखाएँ बनाते हैं, तो चरम सीमाएँ अधिक स्पष्ट रूप से दिखाई देती हैं:

निम्न उदाहरण से पता चलता है कि न्यूनतम स्कफेल फ़ंक्शन को खोजने के लिए आनुवंशिक मॉड्यूल का उपयोग कैसे करें। आप इस उदाहरण को स्रोत कोड में उदाहरणों / जेनेटिक- schwefel फ़ोल्डर में पा सकते हैं।

//!    . //! //! y = f(x),  x = (x0, x1, ..., xi,... xn). //!      x' = (420.9687, 420.9687, ...) //!      xi - [-500.0; 500.0]. //! f(x') = 0 //! //! #  //! * ` ` -   . y = f(x). //! * `` -    , x = (x0, x1, x2, ..., xn). //! * `` -   x    . //! * `` -  . //! * `` -    . use optlib::genetic; use optlib::genetic::creation; use optlib::genetic::cross; use optlib::genetic::goal; use optlib::genetic::logging; use optlib::genetic::mutation; use optlib::genetic::pairing; use optlib::genetic::pre_birth; use optlib::genetic::selection; use optlib::genetic::stopchecker; use optlib::testfunctions; use optlib::Optimizer; ///    type Gene = f32; ///   type Chromosomes = Vec<Gene>; fn main() { //   //  .  xi     [-500.0; 500.0] let minval: Gene = -500.0; let maxval: Gene = 500.0; //      let population_size = 500; //   xi  . //  15-   let chromo_count = 15; let intervals = vec![(minval, maxval); chromo_count]; //      ( ) //      optlib::testfunctions let goal = goal::GoalFromFunction::new(testfunctions::schwefel); //       . // RandomCreator       . let creator = creation::vec_float::RandomCreator::new(population_size, intervals.clone()); //        //     . let partners_count = 2; let families_count = population_size / 2; let rounds_count = 5; let pairing = pairing::Tournament::new(partners_count, families_count, rounds_count); //   //      , //   -     let single_cross = cross::FloatCrossExp::new(); let cross = cross::VecCrossAllGenes::new(Box::new(single_cross)); //    //    (     ). let mutation_probability = 15.0; let mutation_gene_count = 3; let single_mutation = mutation::BitwiseMutation::new(mutation_gene_count); let mutation = mutation::VecMutation::new(mutation_probability, Box::new(single_mutation)); // .       , //     . let pre_births: Vec<Box<genetic::PreBirth<Chromosomes>>> = vec![Box::new( pre_birth::vec_float::CheckChromoInterval::new(intervals.clone()), )]; //    //   ,       1e-4 //   3000  (). let stop_checker = stopchecker::CompositeAny::new(vec![ Box::new(stopchecker::Threshold::new(1e-4)), Box::new(stopchecker::MaxIterations::new(3000)), ]); //    .  -   . //        NaN  Inf. //    ,     . let selections: Vec<Box<dyn genetic::Selection<Chromosomes>>> = vec![ Box::new(selection::KillFitnessNaN::new()), Box::new(selection::LimitPopulation::new(population_size)), ]; //     . //       , //       . let loggers: Vec<Box<genetic::Logger<Chromosomes>>> = vec![ Box::new(logging::StdoutResultOnlyLogger::new(15)), Box::new(logging::TimeStdoutLogger::new()), ]; //     let mut optimizer = genetic::GeneticOptimizer::new( Box::new(goal), Box::new(stop_checker), Box::new(creator), Box::new(pairing), Box::new(cross), Box::new(mutation), selections, pre_births, loggers, ); //    optimizer.find_min(); }

यह उदाहरण स्रोत रूट से कमांड चलाकर चलाया जा सकता है

 cargo run --bin genetic-schwefel --release

परिणाम कुछ इस तरह दिखना चाहिए:

 Solution: 420.962615966796875 420.940093994140625 420.995391845703125 420.968505859375000 420.950866699218750 421.003784179687500 421.001281738281250 421.300537109375000 421.001708984375000 421.012603759765625 420.880493164062500 420.925079345703125 420.967559814453125 420.999237060546875 421.011505126953125 Goal: 0.015625000000000 Iterations count: 3000 Time elapsed: 2617 ms

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

GeneticOptimizer संरचना की find_min () विधि आनुवंशिक एल्गोरिथ्म के निष्पादन को शुरू करती है।

मूल प्रकार और वस्तुएँ

ऑप्टलिब मॉड्यूल के मूल लक्षण

ऑप्टलिब लाइब्रेरी को इस उद्देश्य के साथ विकसित किया गया था कि भविष्य में नए ऑप्टिमाइज़ेशन एल्गोरिदम जोड़े जाएंगे ताकि प्रोग्राम आसानी से एक ऑप्टिमाइज़ेशन एल्गोरिदम से दूसरे में जा सके, इसलिए ऑप्टलिब मॉड्यूल में ऑप्टिमाइज़र विशेषता शामिल है, जिसमें एक एकल विधि शामिल है - find_min (), जो निष्पादन पर अनुकूलन एल्गोरिथ्म चलाता है। यहां टाइप T ऑब्जेक्ट का प्रकार है, जो समाधान खोज स्थान का एक बिंदु है। उदाहरण के लिए, उपरोक्त उदाहरण में, यह वीईसी <जीन> है (जहां जीन एफ 32 के लिए एक उपनाम है)। यही है, यह वह प्रकार है जिसका उद्देश्य उद्देश्य फ़ंक्शन के इनपुट को खिलाया जाता है।

ऑप्टिमाइज़र विशेषता को ऑप्टिब मॉड्यूल में निम्नानुसार घोषित किया गया है:

 pub trait Optimizer<T> { fn find_min(&mut self) -> Option<(&T, f64)>; }

Optim_ trait's find_min () पद्धति में ऑब्जेक्ट का एक विकल्प लौटना चाहिए <(& T, f64)>, जहाँ & T में दिए गए टुपल का समाधान पाया जाता है, और f64 के समाधान के लिए ऑब्जेक्टिव फ़ंक्शन का मान है। यदि एल्गोरिथ्म एक समाधान नहीं ढूंढ सका, तो find_min () फ़ंक्शन को कोई भी नहीं लौटना चाहिए।

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

एक एजेंट, बदले में, एक संरचना है जो ऑप्टलिब - एजेंट से एक और विशेषता को लागू करता है।

एलगोरिदमविथगेंट और एजेंट के लक्षण ऑप्टिलिब मॉड्यूल में निम्नानुसार घोषित किए गए हैं:

 pub trait AlgorithmWithAgents<T> { type Agent: Agent<T>; fn get_agents(&self) -> Vec<&Self::Agent>; } pub trait Agent<T> { fn get_parameter(&self) -> &T; fn get_goal(&self) -> f64; }

दोनों एल्गोरिथ्मविथगेंट और एजेंट के लिए, टाइप टी का ऑप्टिमाइज़र के लिए एक ही अर्थ है, अर्थात, यह ऑब्जेक्ट का प्रकार है जिसके लिए उद्देश्य फ़ंक्शन के मूल्य की गणना की जाती है।

GeneticOptimizer संरचना - आनुवंशिक एल्गोरिथम कार्यान्वयन

दोनों प्रकार GeneticOptimizer संरचना के लिए कार्यान्वित किए जाते हैं - ऑप्टिमाइज़र और एल्गोरिथ्मविथागैगेंट्स।

आनुवंशिक एल्गोरिथम के प्रत्येक चरण को अपने स्वयं के प्रकार द्वारा दर्शाया जाता है, जिसे खरोंच से लागू किया जा सकता है या ऑप्टिलिब :: आनुवंशिक कार्यान्वयन में से किसी एक का उपयोग कर सकता है। आनुवंशिक एल्गोरिथम के प्रत्येक चरण के लिए ऑप्टलिब :: आनुवंशिक मॉड्यूल के अंदर सहायक संरचनाओं और कार्यों के साथ एक सबमॉड्यूल होता है जो आनुवंशिक एल्गोरिथम के चरणों के सबसे अधिक बार उपयोग किए जाने वाले एल्गोरिदम को लागू करता है। इन मॉड्यूल के बारे में नीचे चर्चा की जाएगी। इन सबमॉड्यूल्स में से कुछ के अंदर भी एक vec_float सबमॉड्यूल होता है जो कि उद्देश्य फ़ंक्शन के फ्लोटिंग-पॉइंट नंबरों (f32 या f64) के वेक्टर से गणना किए जाने पर केस के लिए एल्गोरिदम के चरणों को लागू करता है।

GeneticOptimizer संरचना का निर्माण निम्नानुसार घोषित किया गया है:

 impl<T: Clone> GeneticOptimizer<T> { pub fn new( goal: Box<dyn Goal<T>>, stop_checker: Box<dyn StopChecker<T>>, creator: Box<dyn Creator<T>>, pairing: Box<dyn Pairing<T>>, cross: Box<dyn Cross<T>>, mutation: Box<dyn Mutation<T>>, selections: Vec<Box<dyn Selection<T>>>, pre_births: Vec<Box<dyn PreBirth<T>>>, loggers: Vec<Box<dyn Logger<T>>>, ) -> GeneticOptimizer<T> { ... } ... }

GeneticOptimizer का निर्माण कई प्रकार की वस्तुओं को स्वीकार करता है जो आनुवंशिक एल्गोरिथम के प्रत्येक चरण को प्रभावित करता है, साथ ही परिणामों का उत्पादन भी करता है:

लक्ष्य: बॉक्स <dyn लक्ष्य <टी >> - उद्देश्य समारोह;
stop_checker: बॉक्स <dyn stopChecker <T >> - स्टॉप मानदंड;
निर्माता: बॉक्स <dyn निर्माता <टी >> - प्रारंभिक जनसंख्या बनाएं;
बाँधना: बॉक्स <डायन जोड़ी <टी >> - क्रॉसिंग के लिए भागीदारों का चयन करने के लिए एल्गोरिथ्म;
क्रॉस: बॉक्स <डायन क्रॉस <टी >> - क्रॉसिंग एल्गोरिदम;
उत्परिवर्तन: बॉक्स <dyn उत्परिवर्तन <टी >> - उत्परिवर्तन एल्गोरिथ्म;
चयन: वीईसी <बॉक्स <डायन चयन <टी> >> - चयन एल्गोरिदम का एक वेक्टर;
pre_births: Vec <Box <dyn PreBirth <T> >> - व्यक्तियों को बनाने से पहले असफल गुणसूत्रों को नष्ट करने के लिए एल्गोरिदम का एक वेक्टर;
लकड़हारे: Vec <Box <dyn Logger <T> >> - वस्तुओं का एक वेक्टर जो आनुवंशिक एल्गोरिथ्म के लॉग को संरक्षित करता है।

एल्गोरिथ्म को चलाने के लिए, आपको ऑप्टिमाइज़र विशेषता के find_min () विधि को निष्पादित करने की आवश्यकता है। इसके अलावा, GeneticOptimizer संरचना में next_iterations () विधि है, जिसका उपयोग find_min () विधि पूर्ण होने के बाद गणना जारी रखने के लिए किया जा सकता है।

कभी-कभी एल्गोरिथ्म को रोकने के बाद, एल्गोरिदम के मापदंडों या उपयोग किए गए तरीकों को बदलना उपयोगी होता है। यह जेनेटिकओप्टिमाइज़र संरचना के निम्नलिखित तरीकों का उपयोग करके किया जा सकता है: प्रतिस्थापन_पेयरिंग (), रिप्लेस_क्रॉस (), रिप्लेसमेंट_मुटेशन (), रिप्ले_पर_बर्थ (), रिप्लेसमेंट_सेलेक्शन (), रिप्ले_स्टॉप_कैचर ()। इन विधियों से आप जेनेटिकऑप्टिमाइज़र संरचना में निर्मित विशेषता वस्तुओं को प्रतिस्थापित कर सकते हैं जब इसे बनाया जाता है।

आनुवंशिक एल्गोरिथ्म के मुख्य प्रकारों की चर्चा निम्न वर्गों में की जाती है।

लक्ष्य विशेषता - उद्देश्य समारोह

लक्ष्य लक्षण को ऑप्टिब में घोषित किया गया है :: आनुवंशिक मॉड्यूल निम्नानुसार है:

 pub trait Goal<T> { fn get(&self, chromosomes: &T) -> f64; }

दिए गए गुणसूत्र के लिए उद्देश्य फ़ंक्शन का मान प्राप्त करें।

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

निर्माता गुण - एक प्रारंभिक जनसंख्या का निर्माण

निर्माता गुण प्रारंभिक आबादी के "निर्माता" का वर्णन करता है। इस लक्षण को इस प्रकार घोषित किया गया है:

 pub trait Creator<T: Clone> { fn create(&mut self) -> Vec<T>; }

बनाने () विधि को गुणसूत्रों के वेक्टर को उसी आधार पर वापस करना चाहिए, जिसके आधार पर प्रारंभिक जनसंख्या बनाई जाएगी।

ऐसे मामले के लिए जहां कई फ्लोटिंग-पॉइंट नंबरों का एक फ़ंक्शन ऑप्टिमाइज़ किया गया है, Optlib :: आनुवंशिक :: निर्माता :: vec_float मॉड्यूल में एक यादृच्छिक तरीके से गुणसूत्रों के प्रारंभिक वितरण को बनाने के लिए एक RandomCreator <G> संरचना है।

इसके बाद, टाइप <G> क्रोमोसोम वेक्टर में एक गुणसूत्र का प्रकार होता है (कभी-कभी "जीन" शब्द का उपयोग "गुणसूत्र" शब्द के बजाय किया जाता है)। मूल रूप से, टाइप <G> का अर्थ होगा F32 या f64 यदि गुणसूत्र Vec <f32> या Vec <f64> प्रकार हैं।

RandomCreator <G> की संरचना निम्नानुसार घोषित की गई है:

 pub struct RandomCreator<G: Clone + NumCast + PartialOrd> { ... }

यहाँ NumCast num crate से एक प्रकार है। यह प्रकार आपको () विधि का उपयोग करके अन्य संख्यात्मक प्रकारों से एक प्रकार बनाने की अनुमति देता है।

रैंडम क्रिएटर <जी> संरचना बनाने के लिए, आपको नए () फ़ंक्शन का उपयोग करने की आवश्यकता है, जिसे निम्नानुसार घोषित किया गया है:

 pub fn new(population_size: usize, intervals: Vec<(G, G)>) -> RandomCreator<G> { ... }

यहाँ जनसंख्या_साइज जनसंख्या का आकार (निर्मित होने वाले गुणसूत्रों की संख्या) है, और अंतराल दो तत्वों के ट्यूपल्स का सदिश है - गुणसूत्रों के सेट में संबंधित गुणसूत्र (जीन) का न्यूनतम और अधिकतम मूल्य, और इस वेक्टर का आकार निर्धारित करता है कि गुणसूत्रों के सेट में कितने गुणसूत्र शामिल हैं। प्रत्येक व्यक्ति।

ऊपर दिए गए उदाहरण में, Schweffel फ़ंक्शन को 15 चर प्रकार f32 के लिए अनुकूलित किया गया था। प्रत्येक चर की सीमा [-500] में होनी चाहिए; 500]। यही है, जनसंख्या बनाने के लिए, अंतराल वेक्टर में 15 ट्यूपल्स (-500.0f32, 500.0f32) होने चाहिए।

टाइपिंग जोड़ी - पार करने के लिए भागीदारों का चयन

पेयरिंग विशेषता का उपयोग उन व्यक्तियों का चयन करने के लिए किया जाता है जो इंटरब्रिड होंगे। इस लक्षण को इस प्रकार घोषित किया गया है:

 pub trait Pairing<T: Clone> { fn get_pairs(&mut self, population: &Population<T>) -> Vec<Vec<usize>>; }

Get_pairs () विधि जनसंख्या संरचना के लिए एक संकेतक लेती है, जिसमें जनसंख्या के सभी व्यक्ति शामिल हैं, और इस संरचना के माध्यम से आप आबादी में सबसे अच्छे और सबसे खराब व्यक्तियों का पता लगा सकते हैं।

युग्मन get_pairs () विधि को एक वेक्टर वापस करना चाहिए जिसमें वैक्टर होते हैं जो व्यक्तियों के सूचकांकों को संग्रहीत करते हैं जो परस्पर जुड़े होंगे। क्रॉसिंग एल्गोरिदम (जो अगले भाग में चर्चा की जाएगी) के आधार पर, दो या अधिक व्यक्ति पार कर सकते हैं।

उदाहरण के लिए, यदि इंडेक्स 0 और 10, 5 और 2, 6 और 3 वाले व्यक्ति पार हो जाते हैं, तो get_pairs () विधि को वेक्टर vec लौटना चाहिए! [Vec! [0, 10], vec! [5, 2], vec! ६, ३]]।

ऑप्टलिब :: आनुवंशिक :: युग्मन मॉड्यूल में दो संरचनाएं होती हैं जो विभिन्न भागीदार चयन एल्गोरिदम को लागू करती हैं।

रैंडमपेयरिंग संरचना के लिए, पेयरिंग प्रकार को इस तरह से लागू किया जाता है कि पार्टनर्स को बेतरतीब ढंग से क्रॉसिंग के लिए चुना जाता है।

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

टूर्नामेंट संरचना निर्माता निम्नानुसार घोषित किया गया है:

 pub fn new(partners_count: usize, families_count: usize, rounds_count: usize) -> Tournament { ... }

यहां:

Partners_count - पार करने के लिए व्यक्तियों की आवश्यक संख्या;
family_count - "परिवारों" की संख्या, अर्थात उन व्यक्तियों के सेट जो संतान उत्पन्न करेंगे;
राउंड_काउंट - टूर्नामेंट में राउंड की संख्या।

टूर्नामेंट विधि के एक और संशोधन के रूप में, आप यादृच्छिक संख्या जनरेटर का उपयोग कर सकते हैं, जो उद्देश्य फ़ंक्शन के सबसे खराब मूल्य वाले व्यक्तियों को पराजित करने का एक छोटा सा मौका देता है, अर्थात। उद्देश्य समारोह के मूल्य से प्रभावित जीत की संभावना बनाने के लिए, और दो प्रतियोगियों के बीच अंतर अधिक से अधिक, सबसे अच्छा व्यक्तिगत जीतने का मौका अधिक से अधिक, और उद्देश्य समारोह के लगभग समान मूल्यों के साथ, एक व्यक्ति की जीत की संभावना 50% के करीब होगी।

टाइप क्रॉस - क्रॉसिंग

पार करने के लिए, व्यक्तियों के "परिवारों" के गठन के बाद, आपको नए गुणसूत्र वाले बच्चों को प्राप्त करने के लिए उनके गुणसूत्रों को पार करने की आवश्यकता होती है। क्रॉसिंग चरण को क्रॉस प्रकार द्वारा दर्शाया जाता है, जिसे निम्नानुसार घोषित किया जाता है:

 pub trait Cross<T: Clone> { fn cross(&mut self, parents: &[&T]) -> Vec<T>; }

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

ऑप्टलिब :: आनुवंशिक :: क्रॉस मॉड्यूल में संरचनाएं होती हैं, जिसके लिए क्रॉस प्रकार को अलग-अलग क्रॉसिंग एल्गोरिदम के साथ लागू किया जाता है।

VecCrossAllGenes - एक संरचना जो क्रोमोसोम को पार करने के लिए डिज़ाइन की गई है, जब प्रत्येक व्यक्ति में क्रोमोसोम का एक सेट होता है - यह एक वेक्टर है। VecCrossAllGenes कंस्ट्रक्टर क्रॉस ऑब्जेक्ट प्रकार को स्वीकार करता है जो कि मूल गुणसूत्र वैक्टर के सभी तत्वों पर लागू होगा। इस मामले में, मूल गुणसूत्र वैक्टर के आकार का आकार समान होना चाहिए। उपरोक्त उदाहरण VecCrossAllGenes संरचना का उपयोग करता है क्योंकि उपयोग किए गए व्यक्तियों में गुणसूत्र Vec <332> प्रकार है।
CrossMean एक ऐसी संरचना है जो दो संख्याओं को इस तरह से पार करती है कि बेटी गुणसूत्र के रूप में मूल गुणसूत्रों के अंकगणितीय माध्य के रूप में गणना की जाएगी।
फ्लोटक्रॉसजीमेट्रिक एक संरचना है जो दो संख्याओं को इस तरह से पार करती है कि एक बेटी गुणसूत्र के रूप में मूल गुणसूत्रों के ज्यामितीय माध्य के रूप में गणना की जाएगी। गुणसूत्रों के रूप में फ्लोटिंग पॉइंट संख्या होनी चाहिए।
क्रॉसबीटवाइज - दो अंकों की बिटवाइज़ सिंगल-पॉइंट क्रॉसिंग।
फ्लोटक्रॉसएक्सपीपी - फ्लोटिंग पॉइंट नंबरों का एक बिट क्रॉसिंग। स्वतंत्र रूप से मंटिसा और माता-पिता प्रदर्शक पार करते हैं। बच्चे को माता-पिता में से एक से संकेत मिलता है।

ऑप्टलिब :: आनुवंशिक :: क्रॉस मॉड्यूल में विभिन्न प्रकारों के बिटवाइज़ क्रॉसिंग संख्याओं के लिए फ़ंक्शंस होते हैं - पूर्णांक और फ्लोटिंग पॉइंट।

म्यूटेशन टाइप करें - म्यूटेशन

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

 pub trait Mutation<T: Clone> { fn mutation(&mut self, chromosomes: &T) -> T; }

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

ऑप्टिब में कुछ उत्परिवर्तन एल्गोरिदम पहले से ही लागू हैं : आनुवंशिक :: उत्परिवर्तन मॉड्यूल।

उदाहरण के लिए, इस मॉड्यूल में VecMutation संरचना है, जो VecCrossAllGenes संरचना के समान कार्य करती है, अर्थात। यदि गुणसूत्र एक वेक्टर है, VecMutation Mutation ऑब्जेक्ट प्रकार को स्वीकार करता है और इसे वेक्टर के सभी तत्वों के लिए दिए गए प्रायिकता के साथ लागू करता है, उत्परिवर्तित जीन (गुणसूत्र वेक्टर के तत्व) के साथ एक नया वेक्टर बनाता है।

ऑप्टलिब :: जेनेटिक :: म्यूटेशन मॉड्यूल में बिटवाइज़्मुटेशन संरचना भी होती है, जिसके लिए म्यूटेशन गुण लागू किया जाता है। यह संरचना दी गई गुणसूत्र में यादृच्छिक बिट्स की संख्या को संक्रमित करती है। यह संरचना VecMutation संरचना के साथ एक साथ उपयोग करने के लिए सलाह दी जाती है।

प्रीबर्थ लक्षण - पूर्व चयन

क्रॉसिंग और म्यूटेशन के बाद, चयन चरण आमतौर पर होता है, जिस पर सबसे असफल व्यक्ति नष्ट हो जाते हैं। हालांकि, ऑप्टलिब में आनुवंशिक एल्गोरिथम के कार्यान्वयन में :: आनुवंशिक पुस्तकालय, चयन कदम से पहले, एक और कदम है जिस पर असफल गुणसूत्रों को त्याग दिया जा सकता है। यह कदम इसलिए जोड़ा गया क्योंकि व्यक्तियों के लिए उद्देश्य फ़ंक्शन की गणना में अक्सर बहुत समय लगता है, और अगर क्रोमोसोम ज्ञात खोज अंतराल में नहीं आते हैं तो इसकी गणना करने की आवश्यकता नहीं है। उदाहरण के लिए, उपरोक्त उदाहरण में, गुणसूत्र जो खंड पर नहीं आते हैं [-500; 500]।

इस तरह के पूर्व फ़िल्टरिंग करने के लिए, PreBirth विशेषता का इरादा है , जिसे निम्नानुसार घोषित किया गया है:

 pub trait PreBirth<T: Clone> { fn pre_birth(&mut self, population: &Population<T>, new_chromosomes: &mut Vec<T>); }

PreBirth विशेषता का एकमात्र प्रीबर्थ () विधि उपरोक्त वर्णित जनसंख्या संरचना का एक संदर्भ है, साथ ही new_chromosomes गुणसूत्र वेक्टर के लिए एक परस्पर संदर्भ है। यह उत्परिवर्तन कदम के बाद प्राप्त गुणसूत्रों का वेक्टर है। प्री_बर्थ () पद्धति के क्रियान्वयन से उन गुणसूत्रों को इस वेक्टर से हटा देना चाहिए जो स्पष्ट रूप से समस्या की स्थिति के लिए उपयुक्त नहीं हैं।

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

CheckChromoInterval संरचना का निर्माण निम्नानुसार है:

 pub fn new(intervals: Vec<(G, G)>) -> CheckChromoInterval<G> { ... }

यहां, निर्माता दो तत्वों के साथ टुपल्स का एक वेक्टर लेता है - गुणसूत्र में प्रत्येक तत्व के लिए न्यूनतम और अधिकतम मूल्य। इस प्रकार, अंतराल वेक्टर का आकार व्यक्तियों के गुणसूत्र वेक्टर के आकार के साथ मेल खाना चाहिए। उपरोक्त उदाहरण में, 15 टुपल्स (-500.0f32, 500.0f32) के एक वेक्टर को अंतराल के रूप में उपयोग किया गया था।

चयन चयन - Selection

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

 pub trait Selection<T: Clone> { fn kill(&mut self, population: &mut Population<T>); }

एक ऑब्जेक्ट जो चयन गुण को मार () विधि में लागू करता है उसे आबादी में प्रत्येक व्यक्ति के लिए व्यक्तिगत संरचना (व्यक्ति) की हत्या () विधि को कॉल करना होगा जिसे नष्ट करने की आवश्यकता है।

आबादी में सभी व्यक्तियों को बायपास करने के लिए, आप एक इटेरेटर का उपयोग कर सकते हैं जो जनसंख्या संरचना के IterMut () विधि को लौटाता है।

चूंकि कई चयन मानदंडों को लागू करना अक्सर आवश्यक होता है, जब जेनेटिकओप्टिमाइज़र संरचना बनाते हैं, तो निर्माणकर्ता चयन ऑब्जेक्ट्स के वेक्टर को स्वीकार करता है।

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

KillFitnessNaN - उन व्यक्तियों को नष्ट कर देता है जिनमें उद्देश्य फ़ंक्शन का मान NaN या Inf होता है।
LimitPopulation - इस तरह के सबसे खराब व्यक्तियों को नष्ट कर देता है ताकि आबादी का आकार किसी दिए गए आकार से अधिक न हो।
ऑप्टलिब :: आनुवंशिक :: चयन :: vec_float :: CheckChromoInterval - यदि फ्लोटिंग-पॉइंट संख्याओं के वेक्टर का कार्य अनुकूलित है, तो यह उन व्यक्तियों को नष्ट कर देता है जिनके गुणसूत्र मान दिए गए अंतराल में फिट नहीं होते हैं। यह संरचना ऑप्टिकली :: आनुवंशिक :: pre_birth :: vec_floatCheckChromoInterval संरचना के पिछले चरण के आनुवंशिक एल्गोरिथ्म के समान काम करती है।

StopChecker विशेषता - मानदंड रोकें

चयन चरण के बाद, आपको यह जांचने की आवश्यकता है कि क्या आनुवंशिक एल्गोरिथम को रोकने का समय है। जैसा कि पहले ही ऊपर उल्लेख किया गया है, इस स्तर पर, आप विभिन्न स्टॉपिंग एल्गोरिदम का भी उपयोग कर सकते हैं। एल्गोरिथ्म के रुकावट के लिए, वह वस्तु जिम्मेदार है जिसके लिए स्टॉपकैचर विशेषता लागू की जाती है, जिसे निम्नानुसार घोषित किया जाता है:

 pub trait StopChecker<T: Clone> { fn can_stop(&mut self, population: &Population<T>) -> bool; }

यदि एल्गोरिथ्म को रोका जा सकता है तो यहां can_stop () विधि सही वापस आनी चाहिए, अन्यथा यह विधि झूठी वापस आनी चाहिए।

ऑप्टलिब :: आनुवांशिक :: स्टॉपकैचर मॉड्यूल में कई संरचनाएँ होती हैं जिनमें बुनियादी रोक मापदंड और अन्य मानदंडों से संयोजन बनाने के लिए दो संरचनाएँ होती हैं:

MaxIterations - पीढ़ी संख्या द्वारा मानदंड को तोड़ें । आनुवंशिक एल्गोरिथ्म दिए गए पुनरावृत्तियों (पीढ़ियों) की एक संख्या के बाद बंद हो जाएगा।
GoalNotChange - एक विराम मानदंड जिसके अनुसार एल्गोरिथ्म को रोकना चाहिए यदि किसी दिए गए पुनरावृत्तियों के लिए एक नया समाधान नहीं मिल सकता है। या दूसरे शब्दों में, यदि दी गई कई पीढ़ियों के लिए अधिक सफल व्यक्ति दिखाई नहीं देते हैं।
थ्रेसहोल्ड - एक स्टॉपिंग मानदंड जिसके अनुसार आनुवांशिक एल्गोरिथ्म बाधित हो जाता है यदि पल में सबसे अच्छा समाधान के उद्देश्य फ़ंक्शन का मान निर्दिष्ट थ्रेशोल्ड मान से कम है।
CompositeAll — , ( - StopChecker). , - , .
CompositeAny — , ( - StopChecker). , - , .

Logger —

Logger , , , . Logger :

 pub trait Logger<T: Clone> { ///       fn start(&mut self, _population: &Population<T>) {} ///     , ///           fn resume(&mut self, _population: &Population<T>) {} ///         /// (    ) fn next_iteration(&mut self, _population: &Population<T>) {} ///      fn finish(&mut self, _population: &Population<T>) {} }

optlib::genetic::logging , Logger:

अंतिम तर्क के रूप में GeneticOptimizer संरचना का निर्माण, लॉगर लक्षण -objects के एक वेक्टर को स्वीकार करता है, जो आपको प्रोग्राम के आउटपुट को लचीले ढंग से कॉन्फ़िगर करने की अनुमति देता है।

अनुकूलन एल्गोरिदम के परीक्षण के लिए कार्य

Schweffel फ़ंक्शन

अनुकूलन एल्गोरिदम का परीक्षण करने के लिए, कई कार्यों का आविष्कार कई स्थानीय विलुप्त होने के साथ किया गया था। मॉड्यूल optlib :: testfunctions कई कार्य है, जो एल्गोरिदम का परीक्षण किया जा सकता है। इस लेखन के समय, ऑप्टलिब :: टेस्टफंक्शंस मॉड्यूल में केवल दो फ़ंक्शन होते हैं।

इन कार्यों में से एक श्वेफेल फ़ंक्शन है, जिसके बारे में लेख की शुरुआत में लिखा गया था। एक बार फिर, मुझे याद है कि यह फ़ंक्शन निम्नानुसार लिखा गया है:

F (x) = 418.9829 N - \sum_{i = 1}^{N} x_{i} \sin (\sqrt{| x_{i} |})

$F(\boldsymbol x) = 418.9829N - \sum_{i=1}^{N}x_i \sin (\sqrt{|x_i|})$

x' = (420.9687, 420.9687, ...). .

optlib::testfunctions schwefel . N .

, , , , .

F (x) = \sum_{i = 1}^{N} (x_{i} - n)^{2}

$F(\boldsymbol x) = \sum_{i=1}^{N} (x_i - n)^2$

x' = (1.0, 2.0,… N). .

optlib::testfunctions paraboloid .

निष्कर्ष

optlib , . ( optlib::genetic ), , , , .

optlib::genetic. . , , , , .

, . , ( , ..)

इसके अलावा, अनुकूलन एल्गोरिदम के परीक्षण के लिए नए विश्लेषणात्मक कार्यों (श्वेफेल फ़ंक्शन के अलावा) को जोड़ने की योजना है।

एक बार फिर, मुझे ऑप्टलिब लाइब्रेरी से जुड़े लिंक याद हैं:

पेज on github - https://github.com/Jenyay/rust-optimization
पेज at crates.io - https://crates.io/crates/optlib
प्रलेखन - https://docs.rs/optlib

मैं आपकी टिप्पणियों, परिवर्धन और टिप्पणियों के लिए तत्पर हूं।

Optlib। जंग में एक आनुवंशिक अनुकूलन एल्गोरिथ्म का कार्यान्वयन