نمایش نتایج: از شماره 1 تا 2 از مجموع 2

موضوع: طراحی الگوریتم

  
  1. #1


    عضو غیر فعال شناسه تصویری hamidch
    تاریخ عضویت
    Jul 2005
    نوشته
    62
    سپاسگزاری شده
    0
    سپاسگزاری کرده
    0

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

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



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

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

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

    در آغاز الگوريتم، تعدادی از افراد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



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

  2. #2
    نام حقيقي: محمد حکیمی

    Administrator شناسه تصویری Hakimi
    تاریخ عضویت
    Dec 2002
    محل سکونت
    تهران
    نوشته
    6,549
    سپاسگزاری شده
    6798
    سپاسگزاری کرده
    1035
    نوشته های وبلاگ
    4
    عالی است و جالب!


    محمد حکیمی
    hakimi [a t] gmail.com

کلمات کلیدی در جستجوها:

انواع روش های crossover

روش های cross over

الگوریتم باینری سرچ

عملگر انتخاب درcrossover

الگوریتم جستجوی ترتیبی

روش تکرار با جایگذاری

الگوریتم سه عدد به صورت صعودی

روش تکرار با جایگزینی

انواع روش های تولید اعداد تصادفی

الگوریتم روش تکرار ساده

الگوریتم باینری سرچ به صورت ترتیبی

الگوریتم چرخ رولت

روش انتخاب چرخ رولت

انواع روشهای تولید اعداد تصادفی

انتخاب چرخ رولت

الگوریتم تکرار و جایگذاری

باینری سرچ در الگوریتم

روش جایگذاری طراحی الگوریتم

مبحث روش جایگذاری با تکرار

انواع crossover

طراحی الگوریتم جست وجوی ترتیبی

الگوریتم تکرار نقطه ساده در مطلب

انواع جستجوها در طراحی الگوریتمالگوريتم چرخ رولتروش تکرار با جای گذاری

برچسب برای این موضوع

مجوز های ارسال و ویرایش

  • شما نمی توانید موضوع جدید ارسال کنید
  • شما نمی توانید به پست ها پاسخ دهید
  • شما نمی توانید فایل پیوست ضمیمه کنید
  • شما نمی توانید پست های خود را ویرایش کنید
  •