طراحی الگوریتم

[hamidch]

با سلام و عرض احترام
من با اجازه شما دوستان یه بخش در مورد الگوریتم رو اینجا قرار می دهم که در مورد روشهای نوین طراحی الگوریتم صحبت بشه .هر چند مبحث ما در نهایت به شیوه های از الگوریتم که در شبکه مورد استفاده قرار می گیرند می رسه ولی فعلا اینجا قرارش دادم که در صورت تشخیص دوستان و مسئولین فروم بعدا در بخش تخصصی شبکه قرار بگیره.
از دوستان محترم که در مورد این مبحث مطالبی رو دارند تقاضا می کنم که مطالبشون رو در این بخش قرار بدهند.



در اولین بحث یک شیوه در طراحی الگوریتم رو به دوستان معرفی می کنم:

الگوريتم ژنتيكي

الگوريتمهای ژنتيکی كه برمبناي ايده تكامل در طبيعت عمل منمايد، برروی جمعيتی از راه‏حلهای بالقوه به جستجوي راه حل نهايي مي‌پردازد. در هر نسل، بهترينهاي آن نسل انتخاب مي‌شوند، و پس از زاد و ولد، مجموعة جديدي از فرزندان را توليد مي‌كنند. در اين فرايند افراد مناسبتر با احتمال بيشتري در نسلهاي بعد باقي خواهند ماند. در الگوريتمهای ژنتيکی، بسياري از مكانيزمهايي كه در زيست‌شناسي وجود دارند، نظير انتخاب بهتر، ترکيب ژنها، جهش ژنها، مهاجرت افراد جمعيت، محلی بودن گونه‌ها و غيره شبيه‏سازی می‏شوند. در اين الگوريتم، جستجو بر روی مجموعه‌اي از راه‌حلها، به صورت موازی انجام می‏شود، در حالي كه در روشهاي سنتي جستجو بصورت ترتيبي ميباشد.

در آغاز الگوريتم، تعدادی از افراد1 - جمعيت اوليه2- به صورت تصادفی ساخته شده و تابع هدف برای تک‏تک آنها ارزيابي مي‌شود. اگر شرط رسيدن به جواب برقرار نباشد( به جواب بهينه نرسيده ‌باشيم )، نسل بعدي با انتخاب والدين براساس ميزان تناسبشان توليد مي‌شوند و فرزندان با احتمالي ثابت دچار جهش مي‌شوند. سپس ميزان تناسب فرزندان جديد محاسبه شده و جمعيت جديد، از جايگزيني فرزندان با والدين ايجاد مي‌شود و اين فرآيند تا برقرار شدن شرط خاتمه تكرار مي‌شود.

الگوريتم ژنتيکی روشي قدرتمند بوده و برروی دسته وسيعی از مسائل به خوبی عمل می‏کند. عمده‌ترين مزاياي اين روش در مقايسه با روشهاي متداول عبارتند از : جستجوي موازي در عوض جستجوي ترتيبي، عدم نياز به هرگونه اطلاعات كمكي نظير روش حل مساله، قطعي نبودن الگوريتم، پياده‌سازي آسان و رسيدن به چند گزينه مطلوب.

همانطور كه گفته شد الگوريتم‌‌ژنتيكي از تعدادي عملگر استفاده مي‌كند که هر يك داراي انواع مختلفي بوده و با روشهاي متفاوتي قابل پياده‌سازي مي‌باشد. برخي از اين عملگرها عبارتند لز:

الف) انتخاب3 : در انتخاب افرادی که نسل جديد را توليد خواهند كرد(والدها) تعيين می‏شوند. اولين قدم در اين راه تعيين شايستگي تك‌تك افراد جمعيت، مي‌باشد كه دو روش براي آن وجود دارد : - تعيين شايستگي متناسب با تابع هدف، تعيين مقدار شايستگي متناسب با رتبة فرد در جمعيت.

در روش رتبه بندي ميزان شايستگي نسبت داده شده به هرفرد تنها به موقعيت او در رتبه‌بندي بستگي دارد و نه مقدار واقعي تابع هدف. اين روش، بسياري از مشكلات موجود در روش شايستگي نسبي را رفع كرده و فشار انتخاب را بسادگي قابل كنترل مي‌سازد. گام بعدي انتخاب افراد بر اساس شايستگي بدست آمده خواهد بود.

يکي از روشهاي انتخاب روش انتخاب بهترين ميباشد. در اين روش، افراد داراي بالاترين رتبه‌ها انتخاب مي‌شوند. ساده‏ترين مکانيزم انتخاب روش انتخاب توسط چرخ رولت4 است که به آن نمونه برداری تصادفي با جايگزينی نيز گفته می‏شود. اين مکانيزم بدين شرح ميباشد: پاره‌خطي به طول واحد در نظر گرفته مي‌شود و به هر فرد قسمتی از پاره‏خط، متناسب با مقدار شايستگي‌اش نسبت داده ‌مي‌شود. سپس به منظور انتخاب، يک عدد تصادفی توليد شده و فردی که عدد در قطعه متعلق به او قرار می‏گيرد، انتخاب مي‌گردد. اين عمل تا انتخاب تمام افراد مورد نياز تكرار مي‌شود. مكانيزم كار، شبيه يک چرخ رولت است که در آن به هر فرد، قطاعي از كل دايره، نسبت داده مي‌شود و هربار با چرخاندن و نگه‌داشتن چرخ، يك قطاع انتخاب مي‌شود.

ب) بازتركيبي : عملگر بازترکيبي، افراد جديدی ( فرزندان) را با استفاده از اطلاعات موجود در والدين توليد می‏کند. بسته به نحوه نمايش ژنها، الگوريتمهايي براي بازتركيبي مقادير صحيح و گسسته وجود دارند. به عمل بازتركيبي در حالت گسسته، كه ژنها به‌صورت زنجيره‌اي از آلل‌ها5 هستند، Crossover گفته مي‏شود.

-crossover تک نقطه‏ای6 :در crossover تک‏نقطه‏اي، يک نقطه k از ميان [1,2,..,Nvar-1] به طور تصادفی و يکنواخت انتخاب می‏شود.(Nvar تعداد متغييرها در هر ژن است ) عمل تركيب با تعويض متغييرها در دوطرف اين نقطه ميان دو والد صورت مي‌پذيرد.( شكل 1- بالا )

-crossover چند نقطه‏ای7 :در اين روش، m نقطه از ميان [1,2,..,Nvar-1] به‌طور تصادفي، بدون تکرار و به صورت صعودی انتخاب می‏شوند. سپس متغييرهای ميان هر دو نقطه متوالی، يكي‌درميان جابجا مي‌شوند. اولين بخش جابجا نخواهد شد. ( شكل 1- پايين )
http://elc.maybod.info/images/ann/113_image001.png

شكل 1- corossorver تك نقطه‌اي(بالا) و چند نقطه‌اي(پايين)

از آنجايي كه اجزای مهم و تاثيرگذار در کروموزومها، لزوما در مجاورت يكديگر قرار نمي‌گيرند، روش چند نقطه‏ای سبب جستجو در تمام فضای جستجو می‏شود. روشهاي ديگري نيز براي عملCrossover وجود دارند ( مانند روش يكنواخت، مخلوط كردن و غيره) كه در اينجا به آنها نمي‌پردازيم.

جهش8: پس از ايجاد هر فرزند، امكان جهش برروي ژنهاي آن وجود دارد، بدين صورت كه مغييرها با احتمال كمي دچار تغييرات كوچكي مي‌شوند. احتمال جهش در هر متغيير با معکوس تعداد متغييرهای موجود در هر كروموزوم متناسب است. هرچه تعداد متغييرها بيشتر باشد احتمال جهش هر متغيير کمتر خواهد شد.

جايگذاری9 : پس از آنکه فرزندان جديد، با استفاده از جمعيت قديمي ساخته شدند و ميزان شايستگی آنها نيز تعيين گرديد، مي‌بايست يک نسل جديد از ميان فرزندان و والدين موجود انتخاب شوند. روشهاي مختلفي براي اين انتخاب وجود دارد كه تحت عنوان جايگذاري شناخته مي‌شود. تعيين روش جايگذاري معمولاّ باتوجه به متد انتخاب صورت مي‌پذيرد.

1 Individuals

2 Initial Population

3 Selection

4 Roulette-wheel Selection

5 اجزاء يك ژن كه مي‌تواند يك عدد دودويي يا طبيعي باشد.

6 Single-Point Crossover

7 Multipoint Crossover

8 Mutation

9 Reinsertion


منبع از سايت:http://elc.maybod.info

---

موضوعات مشابه:

• بازم باز نشدن بعضی از سایتها
• فیلتر کردن تمام سایتها و باز گذاشتن تعدادی محدودی از سایتها
• مشکل باز شدن برخی از سایتها(dns)
• سایتم باز نمیشه

---

[Hakimi]

عالی است و جالب!