بخشی از مقاله
*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***
الگوريتم بهينه سازي تکاملي شکار گروهي دلفين ها (HDA)
چکيده
يکي از حوزه هاي تحقيقاتي مهم که در دهه هاي اخير بسيار مورد توجه بوده ، بهينه سازي ميباشد، که نتيجه آن طراحي انواع مختلفي از الگوريتم ها بوده است . در بسياري از مسائل از جمله مسائل مهندسي معمولا با تابع هدفي روبه رو هستيم که ميخواهيم آن را بهينه کنيم . در روش هاي گروهي ، عوامل با هم همکاري مينمايند و رفتار جمعي تمام عوامل باعث يک همگرايي ميشود. بنابراين روش هاي گوناگوني براي رسيدن به اين نقطه بهينه وجود دارد که قطعا هر کدام از اين روش ها معايبي هم دارند. در اين مقاله الگوريتم شکار گروهي دلفين ها به عنوان يک روش جديد بهينه سازي تکاملي ارائه گرديده است . الگوريتم پيشنهادي با الهام از شکار هوشمندانه و گروهي دلفين ها ارائه گرديده است . در اين روش يک دلفين که طعمه را با استفاده از انعکاس صداي خود پيدا کرده به عنوان رهبر انتخاب ميشود، سپس به ديگر دلفين ها موقعيت طعمه را اطلاع ميدهد. دلفين ها با حلقه زدن به دور طعمه و تنظيم موقعيت خود نسبت به رهبر، به صورت يک مخروط طعمه ها را به سطح آب نزديک کرده و آنها را شکار ميکنند.
نتايج آزمايشات نشان ميدهد که الگوريتم پيشنهادي در مقايسه با ساير الگوريتم ها سريعتر به جواب بهينه ميرسد.
کلمات کليدي
شکار گروهي دلفين ها، الگوريتم شکار، الگوريتم خفاش ، بهينه سازي
١- مقدمه
بيشتر مسائلي که بشر در دنياي واقعي با آنها سروکار دارد، بيش از يک هدف را در بر ميگيرند؛ به طوري که پاسخ بهينه مسأله هنگامي حاصل ميشود که کليه اهداف به حد خاصي از بهينگي رسيده باشند. اين گونه مسائل را بهينه سازي چندهدفه ميناميم . اهداف مطرح در مسائل بهينه سازي چندهدفه ممکن است با هم در تضاد باشند، از اين رو، با مجموعه اي از پاسخ هاي بهينه مواجه خواهيم بود. چون که روش هاي کلاسيک در هر مرحله از اجراي الگوريتم تنها يک پاسخ را ميتوانند بيابند، بنابراين نميتوانند براي يافتن مجموعه اي از پاسخ هاي بهينه مناسب باشند. امروزه الگوريتم هاي تکاملي ابزار مناسبي براي حل مسائل بهينه سازي چندهدفه در نظر گرفته ميشوند[١]. براي مثال استفاده از الگوريتم هاي جستجوي شکار، PSO، گله شيرها، خفاش .
الگوريتم پيشنهادي در اين مقاله از يک حالت تغذيه دلفين ها که به صورت سه بعدي انجام ميشود الهام گرفته شده است .
ساختار ادامه مقاله به شرح زير است : در بخش دوم ، زندگي دلفين ها مورد بررسي قرار ميگيرد. در بخش سوم ، کلياتي از الگوريتم شکار دلفين ها، توابع و معيارهاي ارزيابي تشريح شده است . در بخش چهارم به معرفي الگوريتم پيشنهادي خواهيم پرداخت . در بخش پنجم به ارزيابي الگوريتم پيشنهادي، آزمايش توابع مورد استفاده و معيارهاي ارزيابي تشريح و درنهايت نتايج شبيه سازي ارائه شده است .
٢- زندگي دلفين ها
دلفين ها پستانداران باهوشي هستند که به سبب توانايي و ادراک بالا، در توليد مثل و انتخاب شکار از قابليت هاي ويژه اي برخوردارند.
٢-١- زيست شناسي دلفين ها
دلفين ها پستانداراني دريازي از راسته آب بازسانان هستند که رابطه نزديکي با نهنگ ها و گرازماهيها دارند. اجداد اين جانوران جفت - سماني بودند که نزديک به ٥٠ ميليون سال پيش براي پيدا کردن غذا از خشکي به دريا وارد شدند. به صورت تقريبي ٤٠ گونه دلفين وجود دارد که در ١٧ سرده (Genus) گوناگون رده بندي شده اند. بدن دلفين ها در طي ميليون ها سال به تدريج براي زندگي در آب تطابق يافته است .
دلفين ها و ديگر آب بازسانان براي حرکت در آب باله دارند و دمشان آنها را به جلو ميراند. بدنشان به گونه اي است که براي شناي سريع تر و ماندگاري بيشتر در آب با يک بار نفس گيري مناسب است . نياز آنها به پديد آوردن سامانه هاي عصبي پيشرفته براي پژواکيابي در آب باعث شده است که دلفين ها مغزهاي بزرگ و به نسبت پيچيده تري به دست آورند. چنين قابليتي، تواناييهاي ادراکي بالايي به آن ها بخشيده که باعث شده است در ميان بعضي از آن ها، نوعي فرهنگ نمودار باشد.
دلفين ها نسبت به هم پرخاش نيز ميکنند. هرچه سن يک نر بالاتر رود زخم هاي بيشتري به دليل گاز گرفته شدن توسط ديگر دلفين ها بر بدنش ديده ميشود. دلفين ها اين خشونت را در برابر همديگر براي برتري در ميان گروه و به دست آوردن ماده ها انجام ميدهند، اين خشونت گاهي تا به آنجا پيش ميرود که دلفين بازنده در نبرد ناچار ميشود گروه را ترک کند(انتخاب والدين برازنده ).
بيشتر دلفين ها در درون و خارج از آب بينايي بسيار بالايي دارند و حس شنوايي آنها هم از انسان بالاتر است . حس لامسه دلفين ها هم به نحو مناسبي تکامل يافته است . دلفين ها ميتوانند از طريق کيسه هاي هوايي بيني خود محدوده وسيعي از صداها را توليد کنند حتي با سوت زدن ميتوانند با يکديگر ارتباط برقرار نمايند. محققان بر اين باورند که قسمت اعظم مغز دلفين ها براي برقراري ارتباط مورد استفاده قرار ميگيرد. دلفين ها با سيستم پژواک با ديگر موجودات و محيط اطراف ارتباط برقرار ميکنند[٢]. دلفين به کمک رديابي صوتي در زير آب ، محيط پيرامون ، اشياء و ديگر موجودات را مورد بررسي قرار ميدهد.
بدين صورت که با ارسال امواج صوتي به سوي جسم مورد نظر و انعکاس ، شکل ، اندازه و فاصله ي آن را حدس ميزند. دلفين ها جزو باهوش ترين حيوانات بشمار ميآيند. "براي مثال در جزاير مولاوي که يکي از جزيره هاي دور افتاده آفريقا است سالهاست که ماهيگيران محلي با کمک دلفين ها ماهيگيري خوبي ميکنند. به اينگونه که اين ماهيگيرها در ساعت خاصي از روز تورهاي خود را به صورت افقي در چند متري ساحل پهن ميکنند و دلفين ها هم طبق عادت چندين ساله خود، ماهيها را در اين ساعت از روز به طرف تورها رم ميدهند و با اينکار باعث ميشوند که ماهيهاي رم داده شده به تور ماهيگيران گرفتار شوند[٢]."
اغلب جوامع دلفين ها چندهمسر هستند و دلفين هاي نر و ماده با تعداد گوناگوني دلفين از جنس مخالف آميزش ميکنند. آن ها همچنين براي آميزش وابستگي ويژه اي به گروهي که در آن هستند، ندارند و بيرون رفتنشان از گروه براي مدت زمان محدود و به منظور پيدا کردن شريک جنسي از ميان دسته هاي ديگر امري متداول است (باز ترکيب توليد مثل و جهش ).
دلفين هاي پوزه بطري نر به فرزندکشي شناخته شده هستند. آن ها با کوباندن خود به فرزندان ويا گاز گرفتنشان اين کار را انجام ميدهند.
(در يک بررسي، نيمي از ١٠ فرزندي که به ظاهر توسط پدرانشان کشته شدند، نشانه هاي آشکار جراحت بيروني نداشتند، بلکه در درون بدن آسيب جدي ديده بودند.) با آنکه دليل مشخصي براي چنين رفتاري وجود ندارد، به نظر ميرسد که رفتارهاي پرخاشگرانه ناشي از برتريجويي در گروه در آن نقش داشته باشد (برازش فرزندان ).
"دلفين ها با ايجاد صداهايي به شکل تلگراف يا موسيقي با هم ارتباط برقرار ميکنند. سنسورهاي شنوايي آنها ميتوانند صدايي با بسامد Hz٢٥٠ تا KHz٢٠٠ را دريافت کنند با اين توانايي آنان قادرند تصوير دقيقي از جزئيات زير دريا را با دقتي همانند نقشه يا عکس به هم ابلاغ کنند هرچند فاصله آنها خيلي زياد باشد[٢]" (مشابه الگوريتم خفاش ).
الگوي خواب و بيدارشدن در دلفين ها بسيار با انسان ها و ديگر پستانداراني که روي خشکي زندگي ميکنند، فرق دارد و چنين الگويي نياز به پردازش بيشتري از سوي مغز آن ها دارد. در حالت کلي، دلفين ها در هنگام خواب داراي يک نيمکره مغزي با فعاليت کم و آرام هستند که به آن ها هوشياري کافي براي تنفس و مراقبت در برابر مهاجمان و ديگر خطرهاي احتمالي را ميدهد. در اين هنگام نيمي از مغز استراحت ميکند و نيمه ديگر بيدار باقي ميماند. نشانه هاي مراحل آغازين خواب ميتوانند به صورت همزمان در هر دو نيمکره مغزي پديدار شوند. از آنجا که دلفيني که به صورت کامل به خواب برود، غرق ميشود، اين جانوران بر خلاف انسان ها به تک تک نفس هايشان کنترل کامل دارند(مشابه ازدحام گربه ها).
٢-٢- روش هاي شکار دلفين ها
روش معمول در شکار دلفين ها به اين گونه است که گروهي از آن ها با حلقه زدن به دور ماهيها آن ها را در گوشه اي به شکل توپ گرد هم ميآورند و به سطح آب نزديک کرده و سپس با حمله به اين «توپ طعمه » ماهيهاي سر در گم را شکار ميکنند. در اين روش دلفين ها گرداگرد دسته اي از ماهيها ميچرخند و با ترساندن آنها باعث تجمعشان در سطح آب ميگردند. در اين لحظه دلفين ها يکييکي به اين تجمع نزديک شده و براحتي از ميان اين دسته شکار خود را جدا ميکنند. دلفيني که شکار کرده جاي خود را با يکي از دلفين هاي ديگر که با چرخيدن زير و اطراف دسته ماهيها آنها را اسير کرده است عوض کرده ، تا همه بتوانند از اين سفره بهره ببرند. در اين ضيافت دريايي کوسه ها و مرغان دريايي هم شرکت دارند و بي بهره نميمانند.
شکل ١- شکار به صورت حلقه زدن
روش ديگر شکار نيز با تعقيب ماهيها تا درون آب هاي کم عمق ادامه يافته و در نتيجه با گرفتن آسان تر آن ها همراه است . در کاروليناي جنوبي دلفين هاي پوزه بطري اقيانوس اطلس طعمه را تا گل ولاي کرانه دنبال ميکنندو با زدن دم بر روي گل ولاي کف دريا و ايجاد يک حلقه با آب گل آلود و گيرانداختن ماهيها در عمق کم شکارشان ميکنند.
در يک روش ديگر، دلفين ها در نوار ساحلي با همکاري دو يا سه دلفين و پرتاب کردن ماهيها به بيرون از آب و بر روي ساحل ، آنها را شکار ميکنند.
٣- الگوريتم پيشنهادي جستجوي شکار دلفين ها
وجه اشتراک شکارچياني که به صورت گروهي شکار ميکنند اين است که به دور شکار خود حلقه ميزنند و به مرور زمان حلقه را تنگ تر ميکنند. هر عضوي از گروه موقعيت خود را بر اساس موقعيت خودش و موقعيت ساير افراد گروه تصحيح ميکند. در صورتي که شکار از حلقه شکارچيان بگريزد، آنها دوباره خود را سازماندهي ميکنند تا شکار را محاصره کنند. آنها يک شکار را انتخاب ميکنند و گروه به مرور به آن نزديک ميشود، تا اينکه بتواند آن را شکار کند. در اين الگوريتم هر دلفين نمايانگر يک راه حل براي مساله اي خاص ميباشد. همانند حيوانات واقعي که گروهي شکار ميکنند، حيوانات مصنوعي نيز با يکديگر در گرفتن شکار همکاري ميکنند، منظور از شکار در اينجا يعني نقطه بهينه . موقعيت هر شکارچينسبت به شکار، ميزان شانس آن را در گرفتن شکار تعيين ميکند[٣].
٣-١- مقايسه شکار واقعي و مصنوعي
شکار گروهي دلفين ها و الگوريتم داراي اختلافاتي با يکديگر هستند.
در شکار گروهي ، شکارچيان ميتوانند طعمه را ببينند يا بااستفاده از امواج صوتي خاصي آنرا يافته و موقعيت آن را تشخيص دهند. در مسائل بهينه سازي ما از موقعيت راه حل بهينه هيچ اطلاعي در دست نداريم .
در شکار گروهي دلفين ها، راه حل (طعمه ) پويا ميباشد و دلفين ها (بر اساس موقعيت کنوني طعمه ) بايد موقعيت خود را تصحيح کند.
در مسائل بهينه سازي، راه حل بهينه ثابت است و موقعيت خود را در طول زمان جستجو تغيير نميدهد. هر دو نوع شکار گروهي مصنوعي و واقعي سختيهاي خود را دارند. براي شبيه سازي فرآيند شکار پويا در الگوريتم شکار گروهي ، دلفين ها به سمت رهبر د سته حرکت ميکنند. رهبر، دلفيني است که داراي بهترين موقعيت در شرايط کنوني است . فرض ميشود که رهبر نقطه بهينه را يافته و ساير اعضا به سمت آن حرکت ميکنند. در صورتي که يکي از آنها نقطه اي بهتر را از رهبر کنوني بيابد، در مرحله بعد خود رهبر خواهد شد.
دلفين ها نه تنها به مرور زمان به سمت طعمه حرکت ميکنند (بر اساس موقعيت ساير دلفين ها و موقعيت طعمه ) بلکه موقعيت خود را نيزتصحيح ميکنند. بنابراين در الگوريتم پيشنهادي، بعد از حرکت به سمت رهبر، دلفين موقعيت خود را بر اساس موقعيت ساير اعضا در گروه اصلاح ميکند. در شکار گروهي ، اگر طعمه از حلقه ايجاد شده خارج شود، دلفين ها با سازماندهي مجدد خود دوباره به دور آن حلقه ميزنند. در الگوريتم شکار گروهي اين توانايي به دلفين ها داده شده است تا بتوانند خارج از حلقه را نيز جستجو کنند.
٣-١-١- مراحل الگوريتم
• مقداردهي اوليه مساله بهينه سازي و پارامترهاي الگوريتم
• مقداردهي اوليه گروه دلفين ها (HDA)
• حرکت به سمت رهبر
• اصلاح موقعيت – همکاري ميان اعضا
• سازماندهي مجدد گروه دلفين ها
• کنترل تعداد تکرارهاي الگوريتم
٣-١-٢- مقداردهي اوليه مساله بهينه سازي و پارامترها الگوريتم
HDS: اندازه گروه دلفين ها (تعداد بردارهاي راه حل در شکار گروهي)
MML: بيشترين تعداد حرکت به سمت رهبر
HDCR: نرخ توجه دلفين به گروه که بين ٠ و ١ تغيير ميکند.
MML و HDCR پارامترهايي هستند که براي بهبود موقعيت دلفين (بردار راه حل ) مورد استفاده قرار ميگيرند.
٣-١-٣- مقداردهي اوليه گروه دلفين ها (HD)
براساس تعداد دلفين ها (HDS) ماتريس شکار گروهي با بردارهاي راه حل تصادفي توليد شده پر ميشود. مقدار تابع هدف محاسبه ميشود و رهبر بر اساس مقدار تابع هدف دلفين ها تعيين ميگردد.
٣-١-٤- حرکت به سمت رهبر
موقعيت جديد دلفين ها (بردار راه حل جديد) با حرکت به سمت رهبر به صورت زير توليد ميگردد:
موقعيت جديد دلفين (بردار راه حل جديد):
MML: بيشترين تعداد حرکات به سمت رهبر
and: عدد تصادفي يکنواخت بين صفر و يک
: مقدار موقعيت رهبر براي i مين متغير
براي هر دلفين ، اگر حرکت به سمت رهبر موفقيت آميز باشد، دلفين در موقعيت جديد قرار ميگيرد. ولي در غير اينصورت به موقعيت قبلي خود باز ميگردد.
مقدار MML براي مسائل مختلف متفاوت ميباشد، که بستگي به تعداد تکرارها در هر دوره اجراي الگوريتم دارد که در مرحله ٥ تعريف ميشود.
MML براي تنظيم قابليت انتفاع الگوريتم کاربرد دارد (هرچقدر مقدار آن بيشتر باشد الگوريتم سريعتر همگرا ميشود).
اين پارامتر معمولا مقداري در بازه [٠,٠.٠٥] ميگيرد.
٣-١-٥- اصلاح موقعيت – همکاري ميان اعضا
• در اين مرحله همکاري ميان اعضا به منظور هدايت هرچه بهتر شکار انجام ميپذيرد.
• بعد از حرکت به سمت رهبر، دلفين (بر اساس موقعيت ساير دلفين ها و برخي فاکتورهاي تصادفي) موقعيت ديگري را انتخاب ميکند تا راه حل بهتري را بيابد.
•دلفين ها برايتصحيح موقعيت خود از روش تصحيح مقدار حقيقي استفاده ميکنند.
تصحيح مقدار حقيقي:
موقعيت جديد دلفين از HD بر اساس توجه به شکار گروهي يا تصحيح موقعيت توليد مي شود. بنابراين به هنگام سازي متغيرها به صورت زير انجام ميپذيرد:
