एंटी कॉलोनी ऑप्टिमाइज़ेशन या जेनेटिक एल्गोरिदम प्रतिशत आधारित समस्या

Question

इसलिए मैं हाल ही में वास्तव में एल्गोरिदम के साथ वास्तव में मोहित हो गया हूं। और मैंने हाल ही में टीएसपी को हल करने के लिए एक चींटी कॉलोनी ऑप्टिमाइज़ेशन एल्गोरिदम लागू किया (स्पष्ट रूप से बहुत मजेदार)। अब मैं हल करने के लिए अन्य "समस्याएं" देख रहा हूं। अब मैं एक प्रतिशत आवश्यकता को पूरा करने और मनमानी सीमा से नीचे होने वाली समस्या को हल करने के लिए एक एल्गोरिदम लागू करना चाहता था।

उदाहरण के लिए:

उपयोगकर्ता इनपुट:

1) की सीमा -i.e. खर्च करने के लिए उपलब्ध ऊर्जा की मात्रा।

2) "गुणसूत्र" प्रकार -i.e. नीला (उपप्रकार - इंडिगो, इत्यादि), लाल (उपप्रकार - मारून, आदि), पीला (उपप्रकार - हल्का पीला, आदि) - नीले रंग की तरह प्राथमिक प्राथमिकता में "पूल" चुनने के लिए चयन किया जाता है जिसमें से इंडिगो जैसे विभिन्न उपप्रकार होते हैं, हल्का नीला, समुद्र नीला जो भी हो। -each उप प्रकार के रंग से जुड़ी एक अलग लागत है।

3) "आदर्श" समाधान के लिए आवश्यक प्रकारों का प्रतिशत (अधिक विविधता के लिए अनुमति देने के लिए +/-% पेश कर सकता है)। -i.e. 10% लाल, 30% नीला, 60% पीला।

आउटपुट:

1) संभव अंतिम समाधान है जो दो आवश्यकताओं को पूरा, नीचे जा रहा है - लेकिन के करीब - आवश्यक लागत और supertypes का प्रतिशत आवश्यकताओं को पूरा करने।

तो उदाहरण के लिए।

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

उपयोगकर्ता निर्दिष्ट करता है लागत के रूप में इस प्रकार होना चाहिए = लागत < = 105.

उपयोगकर्ता 25% नीले, पीले 25%, 50% लाल चुनता है। +/- 5% विचलन के साथ

प्रत्येक रंग के लिए उपलब्ध पूल

ब्लू: इंडिगो: लागत = 25; सागर नीला: लागत = 30; नेवी ब्लू: लागत = 75;

पीला: हल्का पीला: लागत = 20; डार्क पीला: लागत = 30; सुपर गहरे पीले (एलओएल): लागत = 75;

लाल: मारून: लागत = 20; रक्त लाल: लागत = 45; चमकदार लाल: लागत = 55;

तो एल्गोरिदम चलाएगा और विभिन्न संयोजनों को वापस करेगा।

संयोजन 1: इंडिगो, गहरा पीला, रक्त लाल: लागत = 100: नीला = 25%, पीला = 30%, लाल = 55%।

संयोजन 2: समुद्र नीले, हल्के पीले रंग की, रक्त लाल: लागत = 105: नीले = ~ 30%, पीले = ~ 20%, लाल = ~ 50%

संयोजन 3: इतने पर और बहुत आगे है।

संपादित करें: दूसरा संपादित

आउटपुट विभिन्न संयोजनों के सेट शामिल होंगे।

उदाहरण के लिए, एक समाधान की तरह संयोजन से मिलकर बनता है हो सकता है:

एक समाधान यह द्वारा प्रतिनिधित्व किया जाएगा:

युग्म 1: लागत = 20; 50% नीला, 25% पीला, 25% लाल;

संयोजन 2: लागत = 30; 10% नीला, 50% पीला, 40% लाल;

संयोजन 3: लागत = 50; 25% नीला, 25% पीला, 50% लाल;

समाधान: = (संयोजन 1, संयोजन 2, संयोजन 3) कुल लागत = 100, और यह x% नीले, वाई% पीले, z% लाल के होते हैं;

आवश्यकताओं के समाधान की तुलना करें, अगर इसे बंद कर दें, तो इसे छोड़ दें।

अंत संपादित

तो मेरे सवाल है। मुझे पता है कि आनुवंशिक एल्गोरिदम काम करेगा। लेकिन क्या एसीओ के कामकाज का भी कार्यान्वयन होगा? उदाहरण के लिए, नीला, पीला और लाल "स्थान" के बराबर होगा, फिर उनके उपप्रकार विभिन्न "सड़कों" का प्रतिनिधित्व करेंगे।

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

संपादित करें: पहले संपादित

मुझे लगता है कि मैं 5 अच्छा अनूठा समाधान करना चाहते हैं निर्दिष्ट करना चाहते हैं (5 एक मनमाना संख्या जा रहा है, 3 हो सकता है, 20 हो सकता है)।

Answer 1

आपका रंग समस्या बहुत मेरे लिए तुच्छ लगता है, यहां तक ​​कि जानवर बल तेजी से हो सकता है, मुझे लगता है कि .. तो अपने चींटी कॉलोनी सबसे शायद यह भी समस्या सिर्फ मैं के लिए अपने प्रतिनिधित्व के साथ देखना हल कर सकते हैं :)

Answer 2

एसीओ, +/- एक्स% है।

प्रत्येक रंग का एक निश्चित प्रतिशत के साथ , तुम बस आगे बढ़ सके, जैसा कि आप ने कहा:

ब्लू पीले और लाल स्थानों विभिन्न उपप्रकार सड़कों का प्रतिनिधित्व करते हैं, और अपने वजन लागत और पर निर्भर आवश्यकता की आवश्यकता है।

तो फिर तुम सिर्फ TSP के लिए के रूप में अपने एओसी विधि लागू होते हैं, लेकिन थोड़ा बदल रहा है कैसे चींटियों को स्थानांतरित: एक पथ के लिए

1. जोड़ने फेरोमोन केवल अगर यह लागत
2. चुनने की कमी fullfills "इष्टतम लंबाई" करने के लिए के = एन% पथ लंबाई निकटतम इष्टतम लागत (उदाहरण में ऊपर, पीले पथ के लिए, एक करीबी से 25% * 95)

आप चल प्रतिशत बाधा तो जोड़ना चाहते हैं:

Cost = X1*light yellow +X2*sea blue+X3*blood red for example. 

अगर यह लागत इष्टतम आप X1 X2 पर कुछ छोटे varations साथ काम कर सकते नहीं है:

मान लीजिए कि आप कर रहे हैं सबसे अच्छा लागत है चलो , Xj ऐसी है किप्रत्येक जोड़ी क्सी के लिए

के लिए उदाहरण X1-ए और X2 + ई द्वारा e*(costseablue-costLightYellow)

उदाहरण के लिए अपनी लागत बदल जाएगा, एक छोटे एप्सिलॉन को देखते हुए: और X3, अपनी लागत अनुकूलन करने के लिए(i और j से जुड़े रंग की लागत) आप Xi को ईपीएसलॉन जोड़ने और Xj से इसे हटाने का प्रयास कर सकते हैं जब तक आप Xi, Xj के सभी जोड़ों के लिए लागत में सुधार नहीं कर सकते।

Answer 3

यदि आपका ग्राफ त्रिभुज असमानता को पूरा करता है तो मैं आपको न्यूनतम स्पैनिंग पेड़ और एक पूर्ण-वजन-गैर-द्विपक्षीय मिलान एल्गोरिदम का प्रयास करने का सुझाव देता हूं। क्रिस्टोफाइड्स एट अल। इष्टतम के 3/2 के भीतर आपको एक समाधान की गारंटी देता है। एक एओसी आपको अच्छा और तेज़ परिणाम दे सकता है, लेकिन आपको इसे कई समस्याओं के लिए अनुकूलित करना होगा। मैंने php (phpclasses.org) में एक क्रिस्टोफाइड एल्गोरिदम लिखा है। इसका प्रयास करने के लिए आपका स्वागत है। मुझे यकीन नहीं है कि यह काम कर रहा है या नहीं। यह कभी-कभी अजीब परिणाम देता है। यह शायद फ्लेरी एल्गोरिदम का मेरा कार्यान्वयन है?