मछली के एक स्कूल के व्यवहार के आधार पर जनसंख्या एल्गोरिदम

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

परिचय

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

जनसंख्या एल्गोरिदम को निम्नलिखित श्रेणियों में विभाजित किया गया है:

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

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

एल्गोरिदम पार्सिंग

इस एल्गोरिथ्म को 2008 में फिलो (बी। फिल्हो) और नेटो (एल। नेटो) द्वारा प्रस्तावित किया गया था।
जैसा कि सभी जनसंख्या एल्गोरिदम में, इनपुट पैरामीटर हैं: फिटनेस फ़ंक्शन (एक फ़ंक्शन जिसके लिए यह एक्स्ट्रेमा खोजना आवश्यक है), इस फ़ंक्शन के अध्ययन का क्षेत्र, और एल्गोरिदम के पैरामीटर (उनके बारे में थोड़ी देर बाद)। वर्तमान FSS एल्गोरिथ्म ( F ish S chool S earch) में, खोज क्षेत्र एक मछलीघर है जिसमें एजेंट (मछली) तैरते हैं। जैसा कि आप जानते हैं, भोजन की तलाश में, मछली एक जाम में तैरती है, इसलिए हमारे मामले में अंतिम लक्ष्य सभी एजेंटों को फ़ंक्शन के चरम क्षेत्र में स्थानांतरित करना है। सामान्य तौर पर, एल्गोरिथ्म ऑपरेशन योजना इस प्रकार है:

1. जनसंख्या का प्रारंभ (मछलीघर में मछली का वितरण भी)
2. एक खाद्य स्रोत के लिए एजेंटों का प्रवासन (सादृश्य: जितना बड़ा कदम समारोह के चरम की दिशा में एजेंटों ने उठाया, उतना ही अधिक भोजन उन्हें प्राप्त हुआ)
3. खोज पूर्ण करें

अधिक जानकारी चाहिए।

मंच "एजेंटों का प्रवासन" पुनरावृति रूप से किया जाता है, और पुनरावृत्तियों में से प्रत्येक में दो समूहों के संचालक निष्पादित होते हैं:

1. एक्वैरियम के भीतर प्रवास के लिए एजेंट प्रदान करने वाले स्विमिंग ऑपरेटर।
2. फीडिंग ऑपरेटरों जो मछलीघर के कुछ क्षेत्रों के अध्ययन की सफलता को रिकॉर्ड करते हैं।

यह उन मापदंडों के बारे में बात करने का समय है जो मछलीघर और उसके निवासियों के पास हैं।
तो, हम निम्नलिखित चर पेश करते हैं जो पूरे मछलीघर की विशेषता हैं:
populationSize आकार - populationSize आकार (स्कूल में मछली की संख्या)।
iterationCount - "एजेंट माइग्रेशन" चरण में पुनरावृत्तियों की संख्या
lowerBoundPoint, higherBoundPoint - lowerBoundPoint, higherBoundPoint ऊपरी और निचली सीमाएं
individStepStart, individStepFinal - एजेंटों के आसपास भोजन खोज की शुरुआत और अंत त्रिज्या सेट करता है
weightScale - अधिकतम एजेंट वजन।
ये बहुत ही पैरामीटर हैं जो उपयोगकर्ता प्रवेश करता है। उनका उपयोग करते हुए, एल्गोरिथ्म की सटीकता / रनटाइम के अनुपात को विनियमित किया जाता है।
एजेंटों को केवल दो मूल्यों की विशेषता है:
swimStatePos - तैराकी के विभिन्न चरणों में एजेंट की स्थिति
weight - वर्तमान एजेंट वजन

बेशक, एल्गोरिथ्म के एक सॉफ्टवेयर कार्यान्वयन के साथ, इस तरह के कई चर स्पष्ट रूप से पर्याप्त नहीं हैं, लेकिन अब हम अपने जीवन को जटिल नहीं करेंगे ।

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

 initialize_randomly_all_fish; while (stop_criterion is not met) { for (each_fish) { individual_movement; evaluate_fitness_function; } feeding_operator; for (each_fish) instinctive_movement; calculate_barycentre; for (each_fish) do { volitive_movement; evaluate_fitness_function; } update_individidual_step; } 

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

1. तो, जैसा कि पहले ही उल्लेख किया गया है, पहला कदम पूरी आबादी को इनिशियलाइज़ करना है: एक्वेरियम के भीतर एजेंट की स्थिति को बेतरतीब ढंग से चुनें ( swimStatePos[0] ) और सभी मछलियों के लिए weight=weightScale/2 को अधिकतम आधा ( weight=weightScale/2 ) के बराबर सेट करें।
2. अगला, एल्गोरिथ्म का मुख्य चक्र शुरू होता है, जो "भोजन स्रोत के लिए एजेंटों के प्रवासन" के चरण की विशेषता है। हमारे मामले में, मान "पुनरावृत्तियों की संख्या" ( iterationCount ) का उपयोग रोक मापदंड के रूप में किया जाता है।
3. इसके बाद तैराकी एजेंटों का व्यक्तिगत चरण आता है। यह इस तथ्य से विशेषता है कि अपने आप के आसपास एक निश्चित क्षेत्र में सभी मछली ( individStep ) फ़ंक्शन के सर्वोत्तम मूल्य को खोजने की कोशिश करते हैं।
   यदि वे सफल होते हैं, तो यह कदम तय है। अन्यथा
   
   हमारा मानना ​​है कि यह आंदोलन नहीं था।
4. अब आपको तैराकी के व्यक्तिगत चरण में सफलता को मजबूत करने की आवश्यकता है। ऐसा करने के लिए, विशेषता "वजन" का उपयोग करें। यह व्यक्तिगत चरण से पहले और बाद में दिए गए एजेंट के लिए फिटनेस फ़ंक्शन में परिवर्तन के बराबर है, जनसंख्या में फ़ंक्शन में अधिकतम परिवर्तन द्वारा सामान्यीकृत: । सामान्यतया, यह इस एल्गोरिथम की एक विशिष्ट विशेषता है, क्योंकि हमें पिछले पुनरावृत्तियों में सर्वश्रेष्ठ एजेंटों को याद रखने की आवश्यकता नहीं है।
5. इसके बाद, मछली तैराकी का अगला चरण बनाती है - सहज सामूहिक। मछली के पूरे स्कूल के लिए, मूल्य "सामान्य माइग्रेशन चरण" की गणना की जाती है: ।
   इसका अर्थ इस प्रकार है: प्रत्येक एजेंट एक पूरे के रूप में पूरी आबादी से प्रभावित होता है, जबकि एक व्यक्तिगत एजेंट का प्रभाव व्यक्तिगत तैराकी चरण में इसकी सफलता के लिए आनुपातिक होता है। फिर पूरी आबादी को गणना मूल्य m द्वारा स्थानांतरित किया जाता है:
   
   
6. अगले तैराकी ऑपरेशन से पहले, मध्यवर्ती चरणों को निष्पादित करना आवश्यक है, अर्थात्: पूरे संयुक्त के गुरुत्वाकर्षण के केंद्र की गणना करने के लिए: ।
7. हम, या बल्कि, मछली, तैराकी के अंतिम चरण में गए: सामूहिक-इच्छा। यहां आपको यह पता लगाने की आवश्यकता है कि पिछले पुनरावृत्ति की तुलना में जनसंख्या का वजन कैसे बदल गया है। यदि यह बढ़ गया है, तो आबादी ने अधिकतम फ़ंक्शन के क्षेत्र से संपर्क किया है, इसलिए, इसकी खोज को संकीर्ण करना आवश्यक है, जिससे गहन गुण प्रकट होते हैं। और इसके विपरीत: यदि संयुक्त का वजन कम हो गया है, तो एजेंट गलत जगह में अधिकतम की तलाश कर रहे हैं, इसलिए आपको प्रक्षेपवक्र की दिशा बदलने और विविध गुणों को दिखाने की आवश्यकता है।
   
   निम्नलिखित सूत्र में collStep का मान collStep पूर्वाग्रह के चरण के लिए जिम्मेदार है। यह एक व्यक्तिगत खोज कदम से 2 गुना बड़े मूल्य का उपयोग करने के लिए अनुशंसित है। dist ऑपरेटर यूक्लिडियन अंतरिक्ष में दो बिंदुओं के बीच की दूरी की गणना करता है।
   
   ( एजेंटों की स्थिति के लिए जिम्मेदार मूल्य एक एन-डायमेंशनल बिंदु के संरचनात्मक प्रकार हैं, जिसके लिए निम्न संचालन को परिभाषित किया गया है: दो बिंदुओं का जोड़ / घटाव, एक बिंदु और संख्या का जोड़ / घटाव, एक बिंदु और एक संख्या का गुणा / भाग और तुलनात्मक बिंदुओं के संचालन से बचने के लिए। इस ज्यामितीय बकवास के अनुसार, इन परिमाणों को वेक्टर डेटा प्रकारों के रूप में माना जाना प्रथागत है, कुछ निश्चित परिचालनों को परिभाषित करना )
8. पुनरावृति में अंतिम ऑपरेटर अगले पुनरावृत्ति के लिए व्यक्तिगत खोज चरण में एक रैखिक कमी है। वास्तव में, यह खोज दक्षता बढ़ाने के लिए पहले से ही मानक एफएसएस एल्गोरिथ्म का एक संशोधन है, जो निम्न सूत्र द्वारा किया जाता है:

कार्यान्वयन और परीक्षण

कार्यान्वयन

इस एल्गोरिथ्म ने मेरे पाठ्यक्रम के काम का आधार बनाया ("मछली के एक स्कूल के व्यवहार से प्रेरित अनुकूलन कार्यक्रम"), जिसे 26 अप्रैल को बचाव में प्रस्तुत किया गया था। शायद किसी को दिलचस्पी होगी कि टर्म पेपर इतनी जल्दी क्यों ले लिए गए। आगे की हलचल के बिना, मैं सिर्फ इतना कहूंगा कि यह उच्च शिक्षा के अर्थशास्त्र के संकाय (पीआई) के 1 वर्ष से छात्रों को निष्कासित करने की योजना का हिस्सा है, जो शैक्षिक इकाई के चंगुल में समाप्त हो गया, जो पूरे वर्ष (सिक्का के पीछे) 30% कटौती की धमकी देता है प्रोपेगैंडा के नारे से भड़कते हैं: "हम सभी को स्वीकार करेंगे, और यदि आवश्यक हो, तो हम अपने खर्च पर सीटों का भुगतान करेंगे")। पाठ्यक्रम के काम की अवधि के ढांचे के भीतर, कार्यान्वयन C # 4.0 में आयोजित किया गया था, OpenTK लाइब्रेरी (.NET के लिए OpenGL आवरण का चयन) को ग्राफिक घटक के रूप में चुना गया था, उपयोगकर्ता-परिभाषित कार्यों को हब से पहले लागू लाइब्रेरी का उपयोग करके पार्स किया गया था । दुर्भाग्य से, मैं स्रोतों को बाहर नहीं कर सकता (कोड एकदम सही है, मुझे खुद कई बार इसका एहसास हुआ है), लेकिन मैं सामान्य विवेक (लेख के अंत में लिंक) पर कार्यक्रम प्रदान करूंगा। इस बीच, मुख्य विंडो का सिर्फ एक स्क्रीनशॉट:

परीक्षण

जनसंख्या-आधारित एल्गोरिदम के लिए, परीक्षण एक आकर्षक चीज है, क्योंकि इसके काम का परिणाम काफी हद तक इनपुट मापदंडों पर निर्भर करता है। इस लेख के भाग के रूप में, हम निम्नलिखित 2 रेखांकन पर विचार करेंगे।

1. 
   
   • खोज क्षेत्र: (-100; -100) से (100; 100)
   • पुनरावृत्तियों की संख्या: 100
   • जनसंख्या का आकार: 50
   • प्रारंभिक व्यक्तिगत चरण: 10
   • अंतिम व्यक्तिगत चरण: 0.1
   • अधिकतम मछली वजन: 50
   
   इसलिए, एल्गोरिथ्म के अंत तक, फ़ंक्शन का अधिकतम मूल्य 9.999978 था ..., और औसत मूल्य 9.999148 है ... औसत मूल्य में परिवर्तन का ग्राफ निम्नानुसार है:
   
   यही है, पहले से ही 15 वीं पुनरावृत्ति पर, मछली का स्कूल ओए अक्ष के साथ सकारात्मक आधा विमान में था। और 48 वें पुनरावृत्ति से शुरू होकर, फ़ंक्शन का औसत मूल्य 9 से नीचे नहीं आया। और यहाँ क्या हो रहा है की पूरी तस्वीर है (हिमखंड की नोक से देखें):
   
   
   
2. 
   
   • खोज क्षेत्र: (-100; -100) से (100; 100)
   • पुनरावृत्तियों की संख्या: 100
   • जनसंख्या का आकार: 50
   • प्रारंभिक व्यक्तिगत चरण: 10
   • अंतिम व्यक्तिगत चरण: 0.1
   • अधिकतम मछली वजन: 50
   
   
   एल्गोरिथ्म के अंत तक, फ़ंक्शन का अधिकतम मूल्य 19.999996 था ... और औसत 19.9994 ... औसत मूल्य की गतिशीलता निम्नानुसार है:
   
   
   पहले से ही 42 पुनरावृत्तियों से, फ़ंक्शन का औसत मूल्य 19 से कम नहीं के स्तर पर रहा। एल्गोरिथ्म मल्टी-एक्सट्रीम फंक्शन्स के साथ कैसे कॉप करता है (हबस्ट्रॉज के लिए फाइल बहुत बड़ी है, इसलिए इसका इमेज इमेज के साथ समस्या हो सकती है):
   

सूत्रों का कहना है

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

पुनश्च

लेख पढ़ने के लिए धन्यवाद! मुझे टिप्पणियों में आपके सवालों का जवाब देने में खुशी होगी।

UPD: स्रोत कोड जोड़े गए।