دانلود با لینک مستقیم و پر سرعت .
نوع فایل: word
قابل ویرایش 60 صفحه
چکیده:
مسائلی در دنیای واقعی وجود دارند که با توجه به اندازه ورودی ( اندازه ورودی به صورت تعداد کاراکتری تعریف می شود که برای نوشتن ورودی لازم است ) در بدترین حالت در زمان چند جمله ایی قابل حل نیستند . برای چنین مسائلی بدست آوردن جواب قطعی در مدت زمان مناسب و هزینه مناسب ، امکان پذیر نبود . بنابراین ایده روش ژنتیک سلولی در علم زیست شناسی ، کمک بسیار شایانی در بدست آوردن جواب بهینه و( درتکرارهای بیشتر جواب قطعی ) کرده است . الگوریتمهای ژنتیکی برای حل مسائل NP-Hard ، طراحی Neural Network ها ،Nonlinear dynamic system ها ،Stragety plannig و... بکار می روند.یکی از موارد استفاده GA در حل مسائل NP-Hard اعمال بر مساله GraphColoring است که ما در این مقاله در این مورد بحث خواهیم کرد.
الگوریتم ژنتیک ، تعاریف ژنتیکی علم زیست شناسی را بصورت انتزاعی و به تبعیت از ژنتیک سلولی پیاده سازی می کند.
مقدمه:
الگوریتمهای ژنتیک بخشی از تحولات رشته کامپیوتر هستند که دارای فضای رشد سریعی در عرصه هوش مصنوعی می باشند.
بطوریکه می توان حدس زد، الگوریتمهای ژنتیک از تئوری داروین که در مورد تکامل تدریجی است، الهام گرفته اند. با نگاه دقیق به روند تکامل، یعنی روندی که طبیعت برای حل مسائل خود از آن استفاده می کند، می توان به ایده های جالب و قابل پیاده سازی رسید. جانوران برای ابقاء خود و ادامه حیات مجبور به سازگاری با محیط هستند. اطلاعات گرفته شده درطی هزاران سال از طبیعت در کروموزومها ودر سطح پایین تر روی ژن ها و دی ان آ ها ذخیره می گردد.
علم کامپیوتر،علمی است که اندیشه آن از زمان تفکر برای اولین ماشین محاسبه گر شروع شد. این علم روز به روز پیشرفت کرد. بطوریکه پیشرفت آن قابل مقایسه با علوم دیگر نیست . این علم تا جائی پیشرغت کرده است که تمامی زندگی روزمره بشررا تحت الشعاع قرار داده است .اعمالی که تا چندین سال پیش با تفکر و حتی نیروی خلاقیت بشر انجام می شد، امروز با استفاده از علم کامپیوتر انجام می گیرد و انجام چنین کارهایی توسط بشر کاری بیهوده و وقت گیر می باشد.
علوم کامپیوتر تنها به پیشرفت در محدوده خود قانع نبوده و متخصصین این علم از علوم دیگری همچون ریاضی و زیست شناسی برای پیشرفت و بهبود آن استفاده می کنند. در این زمینه مکانیزم تکامل انسان و ارث بری خصوصیات از کروموزومها از طریق عملگرهای ژنتیکی توجه متخصصین علم کامپیوتر را به خود جلب کرده است، به گونه ای که آنها برای حل مسائلی که با روشهای معمولی پیدا کردن راه حلهای مناسب برای آنها سخت می باشد این دو علم را با هم ترکیب می کنند.
الگوریتمهای ژنتیک بخشی از تحولات رشته کامپیوتر هستند که دارای فضای رشد سریعی در عرصه هوش مصنوعی می باشند.
بطوریکه می توان حدس زد، الگوریتمهای ژنتیک از تئوری داروین که در مورد تکامل تدریجی است، الهام گرفته اند. با نگاه دقیق به روند تکامل، یعنی روندی که طبیعت برای حل مسائل خود از آن استفاده می کند، می توان به ایده های جالب و قابل پیاده سازی رسید. جانوران برای ابقاء خود و ادامه حیات مجبور به سازگاری با محیط هستند. اطلاعات گرفته شده درطی هزاران سال از طبیعت در کروموزومها ودر سطح پایین تر روی ژن ها و دی ان آ ها ذخیره می گردد.
فهرست مطالب:
چکیده
مقدمه
اطلاعات اولیه علم ژنتیک در طبیعت
تاریخچه ژنتیک
تقسیم بندی علم ژنتیک
تغییرات نسبتهای مندلی
احتمالات
پیوستگی ژنها
جهش ژنی
ژنها و کروموزومها
. متابولیزم RNA
متابولیزم پروتئین
تنظیم بیان ژن
فناوری DNA نوترکیبی
آشنایی با الگوریتم های ژنتیکی ( Genetic
Algorithms )
تاریخچه
زمینه زیست شناسی
مسئله های بغرنج
مسائل NP
چند نمونه از مسائل NP
پیچیدگی محاسباتی و کنترل ناپذیری مقدمه
ای بر نظریه NP
کنترل ناپذیری
تعریف مجدد کنترل ناپذیری
سه گروه کلی مسائل
نظریه NP
مجموعه NP
مسائل NP کامل (NP_Complete)
معرفی یکی از مسائل NP
دسته بندی الگوریتمهای جستجو
الگوریتمهایی برای جستجوی آگاهانه
الگوریتمهای جستجوی محلی
الگوریتم قطعی
الگوریتم حریصانه (Greedy Alg.) ابتدا همه
الگوریتم درخت پوشای حداقل (MST) ابتدا درخت
آتوماتاهای یادگیر
رفتار متقابل محیط و آتوماتای یادگیر
کاربرد آتوماتاهای یادگیر
الگوریتم های ژنتیکی
ویرایش عملگرهای یک الگوریتم ژنتیک
چرخه الگوریتم ژنتیک
تعاریف مقدماتی
ژن
کروموزوم
فضای جستجو
جمعیت ژنتیکی
تابع شایستگی
عملگرهای ژنتیک
انواع روشهای رمزگذاری کروموزوم
انواع روشهای انتخاب
انواع روشهای عمل برش
عملگر برش
انواع روشهای عمل جهش
عملگرجهش روی نمایش باینری
پارامترهای کنترلی
پارامترهای الگوریتم ژنتیک
احتمال برش و احتمال جهش
مقایسه GAs با تکنیکهای دیگر
مزایای الگوریتم ژنتیک در مقایسه با سایر
روشها
کاربردهای الگوریتم ژنتیک
حل مساله Graph-Coloring با استفاده از
الگوریتم ژنتیک
توضیح
نکات جالب مسئله
هدف مسئله پیدا کردن حداقل رنگ برای گراف
ارائه یک راهکار برای حل مسئله فوق
پارامترهای کنترلی
نتیجه گیری
منابع و مراجع
منابع و مأخذ:
[1] D.S.Johnson, and L.A MeGeoch, " Exprimental Analysis of Heuristics for the STSP "
[2] D.E.Goldberg , " Genetict Algorithms in search , optimization and Machine Learning ", Reading MA:Addition-Wesley,1989.
[3] Mars,P.and Narenda.K.S, and Chrystall,M , "Learning Automata Control of Computer Communication Neworks ", proc.of Third Yale workshop on Application of Adoptive System Teheory, Yale Univercity , 1983.
[4] F.busetti ," Genetic Algorithms Overview "
[5] J. Cirasella D.S Johnson, L.A.McGeoch, and W. Zhang, " The Asymmetric Traveling Salesman Problem: Algorithms, Instance Generators, and Tests ",in algorithm Engineering and Experimentation,Third International Workshop, ALENEX 200 Lecture Notes computer Science, Vol.2153,Spring,Berlin,2001,32-59.
[6] M.Grotschel, and O.Holland, " Solution of Large-Scale Symmetric Traveling salesman Problem", Mathematical Programming 51,1991,141-202.
[7] M.Padberg, and G.Rinaldi, "A Branch-And-cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems " ,SLAM Review 33,1991,60-100.
[8] M.Junger, G.Reinelt, and G.Rinaldi, " The Traveling Saleman Problem ", in:Handbooks in Operations Research and Management Science, Volume 7 (M.O.Ball, T.Mangnanti, C.L.Monma, and G.Nemhauser, eds), Elsevier Science B.V., 1995 ,225-330.
[9] Genetic Algorithms Principles And Perspectives A Guide to GA Theory
Colin R.Reeves Jonathan E.Rowe kluwer Academic Publishers
