نوع فایل: word
قابل ویرایش 50 صفحه
چکیده:
در این مقاله ابتدا به معرفی و شرح عملکرد الگوریتم های ژنتیک می پردازیم و عملیات اصلی و پایه در ژنتیک الگوریتم بررسی می شود سپس در مورد چگونگی روند کاری این دسته از الگوریتم ها توضیحاتی داده و با مثالی این مهم را به طور ساده برای شما قابل فهم می کنیم. در ادامه با ا ستفاده از این روش ما مساله جا بجایی معلمان آموزش و پرورش با استفاده از الگوریتم های ژنتیک را حل می کنیم.
کلمات کلیدی
ژنتیک الگوریتم ، Fitness function ، Chromosomes ، Reproduction، Crossover، Mutation
مقدمه:
تا کنون از الگوریتم های ژنتیک برای حل مسائل زیادی استفاده شده است. در مهندسی برای حل مسائل بهینه سازی بسیار از این روش کمک گرفته شده. در اینجا ما قصد داریم با به کارگیری الگوریتم های ژنتیک گامی در جهت حل مشکل جابه جایی معلمان آموزش و پرورش برداریم. در تهیه این متن سعی شده مطالب طوری ارائه شوند که اگر کسی با الگوریتم های ژنتیک آشنایی نداشته باشد تکنیک حل مسئله را دریابد و در انتها دید روشنی نسبت به الگوریتمهای ژنتیک پیدا کند. ابتدا مسأله را به صورت ساده بیان می کنیم یعنی پارامترهای فرعی را حذف کرده و شرط ها و قیودی که باعث پیچیده تر شدن مسأله می گردند نیز کنار می گذاریم. پس از ارائه یک راه حل برای مسأله ساده شده پارامترهای فرعی و شروط را وارد مسأله می کنیم.
به عنوان نمونه می توان از مسایلی مثل کوتاهترین مسیر در شبکه ، مساله فروشنده دوره گرد و... که در آنها به دنبال حداقل و یا حداکثر کردن کمیتی برای حل مسالهمی باشیم ، اشاره نمود هر چند روشهای حل دقیقی برای حل این مسایل وجود دارد ، اما اغلب آنها از درجه پیچیدگی بالایی (NP OR NP_ COPMLETE ) برخوردارند و زمان لازم جهت محاسبه جواب بهینه برای مسایل بزرگ ، بسیار افزایش می یابد .
برای حل مسایلی شبیه مسایل فوق به روش ژنتیک ، ابتدا جوابهای امکان پذیر اولیه را به صورت تصادفی ایجاد می کنیم. این جوابهای اولیه را که به احتمال زیاد بهینه نیستند ، والدین می نامیم.این والدین با عمل تولید مثل ، به تولید فرزندان( جوابهای جدید ) می پردازند .فرزندان حاصل مورد بررسی و ارزیابی قرار گرفته و آن عده که قابل قبول نباشند ( یعنی امکان ناپذیر بوده و یا بهتر از جوابهای قبلی نباشند ) حذف می شوندو فقط فرزندان برگزیده باقی می مانند. تابعی که به بررسی مقبولیت فرزندان حاصل می پردازد ، اصطلاحا تابع FIT نام دارد . والدین اولیه به همراه فرزندان باقی مانده آنها تا این مرحله را نسل اول می نامیم. این مراحل را با فرض فرزندان باقی مانده به عنوان والدین جدید برای تولید نسلهای دوم ، سوم ، ... ادامه می دهیم.
فهرست مطالب:
چکیده
کلمات کلیدی
مقدمه
1الگوریتم های ژنتیک (GA)
1-1اعمال پایه GA
1-1-1 REPRODUCTION تولید
1-1-2CROSS OVERبرش
1-1-3 MUTATION جهش
2صورت مساله
3حل مساله با استفاده از GA
3-1ایجاد جمعیت اولیه
3-2تابع هدف
3-3انتخاب
3-4ترکیب
3-5ایجاد نسل جدید
3-6جهش
3-7بدنه اصلی برنامه
4نتیجه اجرای برنامه
5تغییر تابع هدف
6مراجع و منابع
منابع و مأخذ:
1- طراحی الگوریتم ها با شبه کدهای C++، جعفر نژاد قمی
2- الگوریتم های موازی، سعید راحتی و محمد بهداد
3- طراحی الگوریتم ها، دکتر بهروز قلی زاده
4)Johannes A.Buchman, Introduction to cryptography, springer,2000
5) Using Genetic Algorithm for Parameter
Estimation Yi Wang Computer Science Department , Tsing hua University,100084, Beijing, China
wangy01@mails.tsinghua.edu.cn
September 30, 2004
6) Genetic Algorithms For Classification and Feature Extraction
Min Pei, 1,2 Ying Ding, 2 William F. Punch, III, 3 and Erik D. Goodman 2
1 Beijing Union University, Beijing, China
2 Case Center for Computer-Aided Engineering and Manufacturing
3 Intelligent Systems Laboratory, Department of Computer Science
Michigan State University
Genetic Algorithms Research and Applications Group (GARAGe)
112 Engineering Building
East Lansing, MI 48824
Tel: (517)-353-4973. Fax: (517)-355-7516 e-mail: pei@egr.msu.edu
7)Goldberg, D.E. The Design of Innovation:
Lessons from and for Competent Genetic
- Kluwer, 2002.
8) Milner, R. The Encyclopedia of
- Facts on File, 1990.
Links :
http://www.ciphersbyritter.com/ARTS/MIXNONLI.HTM
http://www.cs.qub.ac.uk/~M.Sullivan/ga/ga_index.html
http://www.math.uno.edu/
http://mathworld.wolfram.com/
An Introduction to Genetic Algorithms - The MIT Press
http://www.Wotsite.org
http://www.issa.orgt
پروژه بررسی الگوریتم ژنتیک با برنامه. doc