بخشی از مقاله

*** این فایل شامل تعدادی فرمول می باشد و در سایت قابل نمایش نیست ***

مقايسه عملکرد دو الگوريتم سيستم جستجوي ذرات باردار (CSS) و الگوريتم ژنتيک (GA) در حل مسائل مقيد با متغيرهاي پيوسته

چکيده
در اين مقاله ابتدا به بيان اصول کلي عملکرد الگوريتم هاي CSS و GA پرداخته مي شود. سپس عملکرد اين دوالگوريتم در حل چند مسأله مقيد با يکديگر مقايسه مي شود. اين مقايسه براي دو پارامترمقدار بهينه تابع هزينه و زمان دستيابي به مقدار بهينه صورت مي پذيرد.با توجه به ماهيت تصادفي هر دو روش براي مقايسه از روش آزمون فرض آماري مجموع رتبه ها (آزمون U) استفاده مي شود.در اين روش براي قضاوت بين عملکرد اين دو الگوريتم از مقدار متوسط و انحراف از معيار در يک نمونه تصادفي استفاده مي شود. بدين ترتيب مي توان به قضاوت بهتري در مورد قدرت عملکرد الگوريتم ها ي فرا کاوشي دست يافت .

١.مقدمه
پس از پيدايش الگوريتم هاي فراکاوشي بهينه سازي، تلاش هاي فراواني براي بيان خصوصيات برتر اين روش ها نسبت به روش هاي قبلي صورت پذيرفته است . يکي از متداولترين اين روشها، مقايسه عملکرد اين الگوريتم ها براي دستيابي به مقدار بهينه تابع هزينه مي باشد.
از آن جا که نقاط شروع اکثر اين الگوريتم ها تصادفي است و همچنين عملکرد اين الگوريتم ها به شدت وابسته به پارامترهاي آن ها مي باشد، دستيابي به مقدار بهينه تابع هزينه بدون در نظر گرفتن هزينه اي که براي اين هدف پرداخته مي شود (زمان حل ) نمي تواند معيار صحيحي براي قضاوت باشد. از طرفي قضاوت تنها به اتکاي يک نقطه (بهترين پاسخ ) بدون در نظر گرفتن مابقي پاسخ هايي که از اجراي برنامه در دفعات متوالي به دست آمده است ، صحيح به نظر نمي رسد.
بهتر آن است که پس از ايجاد چند نمونه تصادفي حاصل از اجراي هر الگوريتم با استفاده از يک آزمون آماري مناسب عملکرد اين الگوريتم ها با يکديگر مقايسه شود. ضمناً در اين مقايسه ها علاوه بر مقدار متوسط بهينه تابع هزينه ،متوسط زماني که براي اين عمليات توسط کامپيوتر صرف مي شود نيز مورد نظر قرار گيرد.

٢.الگوريتم CSS
اين الگوريتم در سال ٢٠٠٩ توسط کاوه و طلعت اهري ارائه شده است [١]. روابط اين الگوريتم براساس قوانين الکتريسيته کولمب و قوانين نيوتن بسط داده شده اند.

روش کار اين الگوريتم را مي توان بصورت زير خلاصه کرد:(شکل ١)


شکل (١)-فلوچارت الگوريتم CSS

الف ) توليد يک سري نقاط تصادفي با توجه به باند مسئله (توليد CPها)
ب ) محاسبه بار الکتريکي هر CP و محاسبۀ نيروي الکتريکي وارد بر هر CP (شکل ٢) ج ) محاسبه مکان جديد هر CP توسط بسط قوانين نيوتن (شکل ٢)
اين الگوريتم داراي يک حافظه CM است که بهترين نتايج وقت الگوريتم را در خود ذخيره مي کند و از اين نتايج براي هدايت ساير CPها و همچنين جايگذاري و اصلاح نقاط خارج شده از باند طراحي استفاده مي کند.


شکل (٢)-خلاصه عملکرد الگوريتم CSS
اين الگوريتم براي به روز رساني بردار هاي طراحي از روابط زير استفاده مي کند:

٣.الگوريتم GA
اساس شکل گيري الگوريتم ژنتيک ، نظريه داروين است . داروين در نظريه خود، طبيعت را داراي يک سير تکاملي مي داند. فرم کنوني اين الگوريتم در سال ١٩٧٥ توسط Holland ارائه شد.
روش کار اين الگوريتم را مي توان حاصل عملکرد سه اپراتور زير دانست :
الف ) اپراتور انتخاب طبيعي: وظيفه اصلي اين اپراتور، امتياز دهي به رشته ها براساس شايستگي آن هاست .
ب ) اپراتور ترکيب متقابل : اين اپراتور با انتخاب تصادفي والدين برتر اقدام به توليد نسل جديد پاسخ ها مي کند.
ج ) اپراتور جهش : اين اپراتور وظيفه ايجاد يک تغيير غيرسازمان يافته را به عهده دارد. ايده اصلي براي استفاده از اين اپراتور، جلوگيري از همگرا شدن به يک مينيمم محلي است .
الگوريتم ژنتيک انواع مختلفي دارد، اما اصول اوليه همه آن ها سه اصل فوق است . الگوريتم ژنتيکي که در اين مقاله به کار برده شده است . علاوه بر سه اصل فوق داراي يک حافظه CM است که بهترين نتايج وقت را در خود ذخيره مي کند و از اين نتايج براي جايگزيني بدترين نقاط و اصلاح نقاط خارج شده از باند طراحي استفاده مي کند.
فلوچارت اپراتور انتخاب طبيعي در شکل (٣) نمايش داده شده است .

در اين مرحله از ميان اعضاي هر نسل با توجه به شانس بقاي هر بردار والدين نسل بعدي بطور تصادفي انتخاب مي شوند. طبيعي است که در اين فرآيند اعضاي برازنده تر، شانس بيشتري براي بقا در سيستم دارند.
نحوه کار اين بخش بدين ترتيب است که ابتدا يک بردار به طول ١٠٠ المان ايجاد مي شود سپس براي هر بردار با توجه به شانس بقاي آن که عددي بين ٠ تا ١٠٠ است مکان هايي تصادفي در اين بردار در نظر گرفته مي شود، پس از آن جايگاه اعضاي اين بردار بطور تصادفي جابه جا مي شود. با توليد يک انديس تصادفي مي توان والدهاي نسل بعد را توليد کرد.
عملکرد اپراتور ترکيب متقابل در برخورد با متغيير هاي پيوسته در شکل (٤) نشان داده شده است .


شکل (٤)-فلوچارت اپراتور ترکيب متقابل

در شکل (٤) Xp١ و Xp٢ به ترتيب والدهاي شماره ١ و ٢ هستند.
اپراتور جهش يک تغيير غير سازمان يافته را به اعضاي نسل جديد اعمال مي کند. توجه شود که اين عمل با احتمال Pm صورت مي پذيرد. شکل (٥)


شکل (٥)-فلوچارت اپراتور جهش

فلو چارت کلي اين الگوريتم در شکل ٦ نشان داده شده است .


شکل (٦)-فلوچارت الگوريتم GA
الگوريتم ژنتيک به عنوان ابزاري کارآمد در بهينه سازي مهندسي در مواردي همچون بهينه سازي هندسي و ابعادي خرپاها، اجزاي محدود، طراحي بهينه سازه ها، بهينه يابي سازه هاي فضاکار [٢] و تحليل بهينه پلاستيک سازه ها [٣] توسط پژوهشگران به کار برده شده است .
٤.آزمون مجموع رتبه ها (آزمون U)
اين آزمون فرض يکي از آزمون هاي ناپارامتري است که براي کاربردهاي آماري به کار مي رود. با استفاده از اين آزمون بدون اين که مجبور باشيم فرض کنيم دو جامعه مورد نمونه گيري داراي توزيع نرمال اند قادر خواهيم بود اين فرض صفر را که از جامعه هاي پيوسته يکساني نمونه مي گيريم در مقابل اين فرض که دو جامعه ميانگين هاي نابرابر دارند آزمون کنيم [٤].
براي اين آزمون از آماره Z که داراي ميانگين  و واريانس ٢ است و بصورت زير تعريف مي شود استفاده مي شود:

در روابط فوق n١ تعداد اعضاي نمونه اول ، n٢ تعداد اعضاي نمونه دوم و W١ مجموع رتبه هاي مقادير نمونه اول مي باشد.منظور از رتبه در اين آزمون جايگاهي است که هر داده در صورتي که دو گروه داده ها را با يکديگر مخلوط کرده و به ترتيب صعودي مرتب کنيم ، به دست مي آورد.

٥. استفاده از تابع جريمه براي حل مسائل مقيد
اکثر روش هاي فراکاوشي بهينه سازي از جمله الگوريتم هاي CSS و GA براي حل مسائل نامقيد فرمول بندي شده اند. يکي از مؤثرترين روش ها براي کاربرد اين الگوريتم ها در حل مسائل مقيد استفاده از تابع جريمه مي باشد که به جاي تابع هزينه اصلي مينيمم مي شود. در اين روش به جاي اعمال قيدها آن ها را با جريمه هاي جايگزين مي کنيم که به ميزان نقض قيدها بستگي داشته باشند [٥].
تابع جريمه به کار برده شده در اين تحقيق بصورت تعريف شده است :

در رابطه (٦) (Q)X تابع هدف نهايي، (fcost)X تابع هزينه ، (gi)x قيد طراحي iام مي باشد.

٦. مثال هاي عددي
در اين بخش براي مقايسه دو الگوريتم CSS و GA عملکرد اين دو الگوريتم در حل چند مسئله مقيد مهندسي باهم مقايسه مي شود.
٦-١ مسئله طراحي بهينه فنرکششي/ فشاري

اين مسئله توسط Belegundu و Arora ارائه شده است . مسئله مورد نظر طراحي فنر کششي/ فشاري با وزن بهينه (کمترين مقدار) مي باشد. قيود مورد نظر براي طراحي حاصل از محدوديت تنش برشي، فاصله حلقه ها و جابه جايي حداقل مي باشد.
هندسه فنر و متغيرهاي طراحي در شکل (٧) نمايش داده شده اند.


شکل (٧)-هندسه فنر و متغييرهاي طراحي

متغيرهاي اين مسئله شامل قطر سيملوله (D)x١، قطر مقطع سيم (d)x٢ و تعداد حلقه ها (N)x٣ مي باشد و تابع هزينه بصورت زير تعريف مي شود:

قيود طراحي نيز بصورت زير در نظر گرفته مي شوند:

باند متغيرهاي پيوسته طراحي بصورت زير در نظر گرفته شده است :

نتايج حاصل از ٣٠ بار حل اين مسئله توسط الگوريتم CSS و الگوريتم GA در جدول (١) و جدول (٢) خلاصه شده است .

در متن اصلی مقاله به هم ریختگی وجود ندارد. برای مطالعه بیشتر مقاله آن را خریداری کنید