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

      و دانلود متن کامل آنها با فرمت ورد اینجا کلیک کنید     

 
دانلود پایان نامه

ساختار کلی یک الگوریتم ژنتیک را می توان به صورت ذیل تصور کرد.
ابتدا پیش از هر چیز باید مکانیسمی برای تبدیل هر جواب مساله به یک کروموزوم تعریف کرد. پس از آن یک مجموعه از کروموزوم ها که در حقیقت مجموعه ای از جواب های مساله هستند به عنوان یک جمعیت آغازینتهیه می گردند. این مجموعه که اندازه آن دلخواه است و توسط کاربر تعریف می شود، اغلب به صورت تصادفی ایجاد می گردد.
بعد از این مرحله باید با بکارگیری عملیات ژنتیک اقدام به ایجاد کروموزوم های جدید موسوم به نوزاد نمود. این عملیات به دو گونه عمده تقاطعی و جهشی تقسیم می شوند. همچنین برای گزینش کروموزوم هایی که باید نقش والدین را بازی کنند دو مفهوم نرخ تقاطعی و نرخ جهشی کاربرد فراوان دارند که این دو نیز پیش از شروع الگوریتم توسط کاربر تعیین می شوند.
بعد از تولید یک سری کروموزوم جدید یا اولاد باید با استفاده از عمل تحول اقدام به انتخاب برازنده- ترین کروموزوم ها نمود. این فرآیند که در فرآیند انتخاب نمود می یابد، گلچین کردن کروموزوم های برازنده در میان والدین و اولاد است، به طوریکه تعداد کروموزوم های منتخب برابر با اندازه جمعیت اولیه باشد. فرآیند انتخابی مبتنی بر مقدار برازندگی هر رشته است. در حقیقت فرآیند ارزیابی محوری ترین بحث در فرآیند انتخاب است.
تا بدین مرحله یک تکرار یا یک نسل از الگوریتم طی شده است. الگوریتم پس از طی چندین نسل به تدریج به سمت جواب بهینه همگرا می شود. شرط توقف مساله نیز طی کردن تعداد معینی تکرار است که پیش از آغاز الگوریتم توسط کاربر تعیین می شود.ساختار کلی یک الگوریتم ژنتیک را بصورت ذیل بیان شده است:
روند الگوریتم ژنتیک
Step 1: Set t:=0
Step 2: Generate initial population, p(t)
Step 3: Evaluate p(t) to create fitness values
Step 4: While (Not termination condition) do:
Recombine p(t) to yield c(t), selecting from p(t) according to
the fitness values.
Evaluate c(t)
Generate p(t+1) from p(t) and c(t)
Set t:=t+1
End.
Step 5:Stop.
فصل چهارم : ارائه مدل ریاضی و الگوریتم پیشنهادی
4-1- مقدمه
معمولا برای ساده سازی و نمادگذاری، از طبقه بندی pos 1/pos 2/pos 3/pos 4/pos 5 در مسائل مکان یابی همانگونه که هاماخر[34] و هاماخر و نیکل [35]، معرفی کرده اند، استفاده می شود. در این طرح طبقه بندی، pos 1 ، تعداد (یا شکل) تسهیلات جدید را مشخص می سازد. در حالتی که می خواهیم برای N1 ، مکان نقاط جدید (، را بیابیم، این مکان، شامل عدد صحیح مثبت می باشد. در pos 2، نوع فضای تصمیم مساله مکان یابی را نشان می دهیم، یعنی، برای مسائل n- بعدی پیوسته، یا p (یا )برای مسائل بر روی سطح. علاوه براین برای شناسایی مسائل مکان یابی شبکه و مسائل مکان یابی گسسته در این مکان بترتیب از نماد Gو D ، استفاده می شود. در این مدل طبقه بندی pos 3 ، برای اختصاص ویژگی های خاص از مساله مکان یابی مفروض می باشد. برای نمونه این مکان، می تواند برای تاکید بر روی تخصیص تسهیلات موجود به تسهیلات جدید در محیط پیوسته باشد که توسط نماد alloc ، نشان داده شده است. همچنین از نماد cap ، برای نشان دادن محدودیت های ظرفیت تسهیلات در محیط گسسته بکار گرفته می شود. در محیط های گسسته، pos 4، شامل هر گونه اطلاعات و محدودیت هایی راجع به هزینه ، می باشد. همچنین در محیط های پیوسته این مکان برای نشان دادن هر گونه اطلاعاتی راجع به تابع فاصله می باشد، برای مثال نشان دهنده فاصله متعامد (منهتن یا پله ای)، نشان دهنده فاصله اقلیدسی است. برای مسائل مکان یابی شبکه، این posبرای مشخص کردن فواصل در شبکه می باشد، خواه فواصل فقط مابین گره های شبکه باشد، و خواه، محاسبه فاصله مابین هر نقطه در گراف باشد، مورد استفاده قرار می گیرد. در این طبقه بندی pos 5 ، نشان دهنده تابع هدف مساله می باشد. برای نمونه اگر یک مسئله وبر یا میانه مدنظر باشد، از نماد در این مکان استفاده می شود. مسائل مرکز با نماد maxو مسائل وبر ترتیبی توسط نشان داده می شوند. همچنین مسائل مکان یابی رقابتی با نماد و تابع هدف مسائل تخصیص درجه دو با نماد QAP نشان داده می شوند. اگر فرض خاصی در هر کدام از مکان ها مدنظر قرار نگیرد، آنگاه این مکان را با نماد یک گلوله (“.”)، نشان می دهند.
خلاصه مبحث فوق این است که، مساله مکان یابی- تخصیص ظرفیت بندی شده با تقاضاهای برنولی در فضای گسسته طبق این دسته بندی از نوعN/D/cap/Bernoulli –demand/●می باشد.
4-2- ساختار مساله
فرض کنید ، یک مجموعه از اندیس های مکان های کاندید برای احداث تسهیلات و ، یک مجموعه از اندیس های مشتریان موجود باشند. در بسیاری از مسائل، درخواست تقاضای مشتریان به وسیله “کمیت”آن تقاضاها مشخص می گردد بدین صورت که مقدار این تقاضاها در واقع مقداری از ظرفیت های تسهیلات هستند که باید استفاده شوند تا این درخواست های تقاضای مشتریان تامین گردند. در این تحقیق، هر درخواست تقاضا یک واحد محسوب می شود، بدین معنی که هر درخواست تقاضا یک واحد از ظرفیت تسهیل مربوطه را مورد استفاده قرار می دهد. درخواست تقاضای هر مشتری به وسیله ی متغیر تصادفی صفر و یک، نشان داده می شود بطوریکه اگر مشتری j ام تقاضا داشته باشد، این متغیر مقدار یک و در غیر اینصورت مقدار صفر می گیرد. از اینرو، در این تحقیق، این امکان پذیر است که تعدادی از مشتریان درخواست تقاضا داشته و تعدادی نداشته باشند.از آنجاییکه درخواست های تقاضای مشتریان از یک تابع توزیع احتمالی پیروی می کند، بنابراین متغیر تصادفی به شکل ذیل بیان می گردد:
جاییکه پارامتر احتمال درخواست تقاضای مشتری j ام را نمایان می سازد. در این تحقیق فرض شده است که متغیر دارای تابع توزیع برنولی می باشد، بنابراین تابع احتمال می تواند به شکل ذیل نوشته شود:
این بدین معنی است که هر مشتری با احتمال دارای تقاضا و با احتمال تقاضا ندارد. نمادگذاری های بکار رفته در این مطالعه در ذیل گرآوری شده اند:
هزینه ثابت برای احداث تسهیل در مکان کاندیدi ام.
دسته بندی : علمی