الگوریتم ژنتیک

سلام

امروز مقاله مون در چین پذیرفته شد و من اول خوشحال بودم ولی بعد که به هزینه رفت و برگشت هتل غذا هزینه خود کنفرانس فکر کردم وتازه فقط مسئله هزینه نیس که مسئله سربازی هم هس روند عجیب غریب نظام وظیفه بدبختی اینه که من تا تا 5 روز دیگه اعزام میشم می گن احتمالا یزد باشه  حالم بدجور گرفته شد . کلی تلاش کن آخرش یه مقاله بشه بعد به جای تشویق بایستی کلی بدبختی برای مراحل بعدیش بکشی .

خدا آخر عاقبت همه مون رو بخیر کنه

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

سلام

و اما بعد

            شهادت حضرت فاطمه زهرا را بر همه عزیزان تسلیت عرض می کنم

     وفات حضرت آیت الله فاضل لنکرانی را بر همه عزیزان تسلیت عرض می کنم

ولی کلا فکر کنم قابل استفاده باشه 

در مورد عکس ها هم باید بگم اگر بالانمیان   بعد بالا امدن کامل وبلاگ راست کلیک کنید و شو پیکچر بزنید درس می شه انشاا.. البته اگه نشد برینhttp://seyedkazemi.blogspot.com

به نام خدا

چکیده مطالب

Leonard M.adleman آزمایش هایی در سال 1994 انجام دادو ثابت کرد که می توان ا ز DNA computing استفاده کرد در حل(direct Hamiltonain path) که یکی از  مسایل معروف NP-camplete problems در علم کامپیوتر است.

این مقاله شرح می دهد روشی را درDNA computing  برای حل مسالهء ((The minimum spanning tree  (مینیممدرخت گسترده).برای به کار بردن این روش باید مجموعهء شهرها کدگذاری شود در

رشته های منفرد  20-mer آلگونکلوتیدی(oligonucleotide) .

حالا فواصل متغیره راه ها بایدرمزگذاری شود در فواصل متفاوت در رشته های آلگونکلوتیدی با دو قسمت   10-mer  ی چسپیده به انتهاها با کدگذاری متناظر راه ها.

بعد از مراحل بعدی مانند:پیوندزنی(هیبرید شدگیhybridization).انعقاد ligation .تقویت بسط توسعه amplification  . بایدDNA  متناوب رمزگذاری شده مسله minimum spanning tree باید تصویه شود و متناوب شود ازباند شامل کوتاهترین طول DNA در ژل الکتروفرسیس   ( حرکت ذرات معلق مایع بوسیله نیروی برق) (electrophoresis) .

لغات کلیدی: DNA computing Hamiltonian path problem minimum spanning tree problem

مقدمه

محاسبات DNA اطلاق می شود به خط مشی DNA  برای محاسبه به وسیله تکنیک های زیست مولکولی برای: کد گذاری اطلاعات وتولید بالقوه راه حل ها و انتخاب وتشخیص درست راه حل.

آدلمان انجام داد آزمایش های پیشگامانه ای در سال 1994 برای ثابت کردن اینکه DNA computing میتواند مورد استفاده قرار گیرد در حل مسله راه مستقیم همیلتون direct Hamiltonian path این مسله اولین بار پیشنهاد شد توسط William Rowan Hamilton 1805-1865 این مسله یک مسله معروف NP-complete  است و به نظر می رسد که وجود ندارد الگوریتم کارایی برای حل این مسله در چند جمله ای های زمانی.

مسله راه همیلتون را می توان به صورت زیر  توصیف کرد:

مجموعه ی مفروض شهرها را با نقاط شروع و پایان  و راه های ارتباطی بین انها در نظر می گیریم . ایا ممکن است که با عبور فقط یک بار از هر شهری از  همه انها عبور کرد؟

قرارداد ادلمان  به این صورت است که :شهرها کد گذاری شود با رشته های منفرد 20-mer الگونکلوتیدی به صورت متمایز( یعنی کد شهرها منحصر به فرد باشد) وراه بین شهرها در رشته های 20-mer الگونکلوتیدی با تناوب تکمیل کنند برای نصف تناوب ارتباط شهرها.

تناوب DNA کدگذاری می کند همه راه حل های بالقوه ای که می تواند تولید شود از پیوند زنی الگونکلوتیدها به نمایندگی شهر ها وراه ها.

بعد از انعقاد پیوند زنی الگونکلوتیدها.تناوب DNA که شروع می شود وپایان می یابد درست در شهرها می تواند تقویت شود  به وسیله PCR polymerase chain reaction با استرهای primers مخصوص.

سپس محصولات PCR می توانند به صورت متناوب  خالص شوند در میان سیستم biotin-avidin magnetic beads به وسیله هر نماینده الگونکلوتیدی در میان شهرها.

تناوب DNA با طول های درست می توانند خالص سازی ژلی gel-purified شود بعد از کار کردن gel electrophoresis.

ترتیب دهی تصویه DNA با طول درست اشکار خواهد کرد جزئیات مسیررا.

عملکرد رله های محاسباتیDNA در منطق هیبریدی (پیوندی) :

توانایی کدگذاری و حل مسائل محاسباتی به وسیله درست جفت کردن و جلوگیری از اشتباه پایه گذاری جفت ها.

به علت اینکه پیوند زنی DNAوابسته است به محاسبات موازی زیادی از ان انتظار می رود که بسیا عالی تر باشد از کامپیوترهای بیس سلیکونی.

مقایسه کامپیوتر های  سیلیکونی متعارف با DNA computing  :

محاسبات سخت افزاریی مبنی بر مواد سیلیکونی – کد گذاری باینری- منطق بولی- وپردازش سریالی

DNA computing   مشخصات متمایزی دارد مثل محاسبات سخت افزاری مبنی بر ملکول های DNA- کد گذاری چهار گانه (کواترنری)-

[i.e. A(Adenine) T(Thymine) G(Guanine) C(Cytosine)]

منطق هیبریدی- محاسبات موازی – و غیره....

در طول چند سال گذشته محاسبات DNA پیشنهاد شده برای حل مسائل مثل: مسله راه  همیلتون – مسله حداکثر مجموعه max  - مسله سوارکار – ساختن جمع اعداد صحیح – برای شکستگی اطلاعات پنهان شده استاندارد متعارف (DES) – 3-SAT problem   متغییر-20 – و در مسله کوتاهترین راه مسافرت فروشنده – و غیره...

این مقاله توضیح می دهد شیوه ی  محاسبات DNA شبیه قرار داد ادلمان در حل مسله مینیم گستردگی درخت .

قرار داد اصلی ادلمان مطرح شده بود برای یافتن راه در مسله راه درست همیلتون. بنابراین پارامترفاصله بین شهرها مورد ملاحضه نبود .

ما پیشنهاد می کنیم به الحاق کردن قطعه از جفت رشته های الگونکلوتیدی به نمایندگی از فاصله بین شهر ها  در رمزگذاری الگو نکلوتیدها ارتباط بین شهر ها.

 بعد از این تغییر اصلاحی در شکل محاسبات الگونکلوتیدی. قرار داد ادلمان می تواند مورد استفاده قرار گیرد در حل مسله ی کمترین گستردگی درخت.

2- دور نما( زمینه) (معلومات قبلی)  

مسله کوچکترین درخت گسترده  :

مسله ی کوچکترین درخت را می توان توضیح داد به صورت ساده به شرح زیر:

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

شیوه مبنی است بر انتقال مستقیم برای پیدا کردن همه ی امکان های درخت گسترده و معیین ساختن همه طول ها.

بعد از مقایسه همهء براوردارزش ها کوچکترین درخت گسترده را می شود پیدا کرد.

با وجود این، این روش می تواند بسیار جامع باشد از انجایی که حالت های ممکن درخت گسترده تمایل دارد به افزایش زیاد همراه با افزایش در خصوص تعداد شهرها.

گراف مخصوص مضطرب در این مقاله نشان داده شده در تصویر  1-A 

و کوچکترین درخت گسترده برای مجموعه ی شهرها داده شده در شکل 1-B ما یازده شهر به عنوان مدل ومجموعه فاصله های بین شهرها را بطور قرار دادی انتخاب می کنیم .

الگوریتم برای مسله ی کوچکترین درخت گسترده :

مرحله اول : ساختن و تولید کردن راه های رندوم در میان گراف

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

مرحله سوم : پیدا کردن کوچکترین درخت گسترده

3- انجام الگوریتم .

3-1- کدگذاری طرح نقشه.

 شکل 2 تصویر کدگذاری درDNA است. ماکدگذاری می کنیم شهرهارا در رشته های منفرد 20-mer ی منحصربه فرد (شکل2-A ) الان متغییر فاصله های راه می تواند کد گذاری شود با فاصله های مختلف به وسیله ی رشته های جفت شده ی الگونکلوتیدی با دو برامدگی کد گذاری شده 10-mer  متناظر با راه که به انتها چسپیده شده است (شکل2-B).

برای مثال فاصله بین شهر های 3 و4 در مجموعه 10 بود بنابراین ما کد گذاری میکنیم 10-bp رشته جفت شده DNA  به نمایندگی فاصله ی  بخش (اینجا،ما تعریف می کنیم    1-bpرشته جفت شده   DNAبرای یک فاصله واحد) درازترین فاصله ما بین شهرها  کد گذاری می شود با درازترین طول رشته یجفت شده DNA.

علاوه بر این قسمت ذکر شده دوتا رشته 10-mer اضافی چسپیده به انتهاهای کدهای متناظر راه برای کدگذاری ما بین شهرها در ملکول DNA  خواهد بود.

برای هر راه مابین  شهرهای i to j رشته جفت شده  DNA  با دو بر جستگی چسپیده به انتها هامی تواند تولید شود به وسیله ی پیوند زن دو تا رشته الگونکلوتیدها:

یکی برای اینکه نماینده فاصله قطعه و نیز دیگری که شامل 3 تا 10-mer از Oi ( oligonucleotide i ) که دنبال شده به وسیله فاصله قطعه و 5 تا 10-mer از Oj

پیاده سازی :

برای پیاده سازیمرحله اول از الگوریتم همه الگونکلوتیدها کد گذاری می شوند  از اطلاعات شهر ها و راه ها (شامل فاصله ها ) .

برای  هر راه Oij ،الگونکلوتید سرویس میدهد به عنوان تراشه ای که به وجود می اورد اتحاد الگو نکلوتیدها را در جهت شهرهای مجاور با هم  برای بسته شدن (انعقاد) تصویر  .(2-c)

از این رو واکنش انعقاد نتیجه می دهد در شکل دادن از مبدا کد گذاری رندوم مولکولی DNA راه ها .پس محصول مرحله یک تقویت می شود توسط PCR استفاده شده اولیه همگانی.

بنا براین ،نمونه    DNAمی تواند تقویت شود .برای اجرا کردن مرحله دوم از الگوریتم محصول مرحله اول باید متناوبا خالص شود میان biotion-avidin magnetic beads  system 

با هر الگونکلوتید نماینده شهرهای در میان امده.فقط رشته منفرد مولکول DNA مکمل همه تناوبها کد گذاری شهرها باید نگه داری شود .

برای اجرای مرحله سوم الگوریتم محصول مرحله دوم باید تقویت شود توسط PCR و جدا شود توسط ژل الکتروفورسیس electrophoresis

بعد از اینکه اطلاعات مسافت ها کد گذاری  شد در راه های الگونکلوتیدها ، ما می توانیم بگوییم شاخه های درخت گسترده را از روی شاخه های موکلول DNA .

کد گذاری متناوب مسله کوچکترین درخت گسترده باید خالص شود و متوالی باشد از باند شامل کوتاه ترین طول از DNA در electrophoresis.

نتایج:

ایجا ما پیشنهاد دادایم روشی را برای محاسبات DNA شبیه قرار دادادلمان در حل مسله مینیم درخت گسترده.

محاسبات مولکو لی DNA نه تنها اطلاعات شهرها را بلکه همچنین اطلاعات فاصله میان شهر ها را کد گذاری می کند.

خالص سازی و توالی باند شامل کوچکترین طول DNA در electrophoresis می تواند پیداکند مسله کوچکترین درخت گسترده را.

                                        والسلام 

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

اگه از دوستان کسی می دونه چیکار باید بکنم راهنمایی کنه...

Permutation Encoding

Crossover

 : Single point crossover يک نقطه Crossover  انتخاب مي شود . از والد اول تا نقطهCrossover  کپي مي شود و والد دوم جستجو مي شود اگر عددهاي والد دوم در فرزند جديد نباشد کپي مي شود .

 توجه : روش هاي زيادي براي ساختن بقيه رشته يعني از نقطه Crossover  به بعد و وجود دارد .

(1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7)

Mutation

Order changing : دو عدد انتخاب مي شود و تغيير مي يابند.

(1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7)

Value Encoding

Crossover

همه انواعCrossover   را مي توان استفاده کرد

Mutation

به اعداد انتخاب  شده  براي Mutation  عداد کوچکي اضافه يا کاسته مي شود .

 (1.29  5.68  2.86  4.11  5.55) => (1.29  5.68  2.73  4.22  5.55)

 تا چند وقت دیگه باید برم سربازی یعنی دقیقا ۸ روز دیگه کلی کار باید انجام بدم ۵۰ روز آموزش احتمالا نتونم  ....

         نتونم چی ؟

 نتونم  به اینترنت دسترسی داشته باشم  و....

دو تا مقاله که یکی ۱۰۰٪ آماده ودیگری ۹۹٪ آماده است داریم باید هر دوشونو سابمیت کنم  این سایت کنفرانس هم آپلود نمی کنه  از دیروز چند بار تلاش کردم البته نمیدونم مشکل از سرعت کم شبکه ی ماست یا سایت اونا

mohsen.seyedkazemi@gmail.com

Crossover and Mutation

Binary Encoding

Crossover

 Crossoverبا نقطه ي منفرد :

ابتدا نقطه ي Crossover point) ) انتخاب مي شود بعد در رشته باينري کروموزوم اول از آغاز رشته تا  نقطه يCrossover  کپي مي شود و از رشته دوم  از نقطه ي Crossover تا پايان کپي مي شود  و فرزند به وجود مي آيد .

البته در شکل زير به وضوح مراحل ذکر شده قابل مشاهده است:

Selection

انتخاب

همان طور که در طرح کلي الگوريتم ژنتيک مطرح گشت ابتدا کروموزوم ها انتخاب مي شود تا والدين نسل بعد باشند و فرآيند هاي Crossover روي آن ها انجام گيرد حال يک سوال اساسي مطرح است که اين انتخاب والدين چگونه وبر چه معياري استوار است . با توجه به نظريه تکاملي داروين     بهترين ها زنده مي مانند براي تواليد نسل هاي آينده .

روش هاي مختلفي براي انتخاب وجود دارد براي مثال :

 (roulette wheel selection , Boltzman selection, tournament selection , rank selection, steady state selection )

چند روش مهم در اينجا توضيح داده مي شود .

http://web.cecs.pdx.edu/~mm/ca-review.pdf

mohsen.seyedkazemi@gmail.com

Genetic Algorithm

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

توضيحات اوليه

الگوريتم ژنتيک از نظريه تکاملي داروين الهام گرفته شده است . در روش هاي حل مسله به وسيله يGA  از فرايند تکاملي براي حل مسله استفاده         مي شود.

الگوريتم با مجموعه راه حل هاي ممکن که با کروموزوم نشان داده مي شود  شروع مي شود و اين مجموعه را Population مي ناميم .

راه حل از يک نسل گرفته مي شود  وبکار مي رود براي توليد نسل جديد با اين اميد که نسل جديد بهتر از نسل قبلي باشد دوباره از نسل جديد با توجه به

(fitness) راه حل هايي جدا مي شود . براي ساختن نسل جديد و اين روند تا زماني ادامه مي يابد که به نتايج راضي کننده برسيم .

طرح کلي الگوريتم ژنتيک

1-       [Start]:ساخته شدن نسل اول به صورت رندوم ازn کروموزم (البته راه حل هاي مناسب براي مسئله) .

2-      [Fitness]: ارزيابي کردن تابع سازگاريf(x) با هر کورموزم x در يک نسل

3-     [New population]: ساختن نسل جديد در مراحل زير :

A. [Selection]: جدا کردن دو کورموزوم مولد براي ساختن نسل با توجه به fitness بهترينfitness انتخاب مي کنيم  که بيشترين شانس را براي انتخاب شدن داراست.

: [Crossover].B با crossover امکان اين را داريم که فرزندان جديدي را علاوه برفرزندان توليد شده به صورت مستقيم از پد ر ومادر توليد کنيم اگر crossover نبود فرزندان الزاماً کپي هايي از پدر و مادر بودند .

 [Mutation] .C     : با mutation امکان  اين را داريم که فرزندان جديد را  

تغيير دهيم در هر بيت ياlocus دلخواه .

.D [Accepting] : مکان فرزند جديد در نسل جديد است .

4-     [Replace]: بکار بردن توليد نسل جديد براي ادامه دوباره ي الگوريتم .

5-     [Test]: اگر شرايط راضي کننده بود بايست و بازگشت به بهترين راه حل در نسل جاري .

6-      [Loop]:رفتن به مرحله 2 .

توضيحات

همان طوري که در طرح کلي GA ديده شد اين الگوريتم خيلي عمومي و کلي است .در مسائل مختلف  مي تواند تعداد پارامترهاي زيادي بکار برده شود .

اولين سوالي که پيش مي آيد اين است که چگونه مي شود کروموزوم ها را ساخت واز چه نوع کدگذاري  استفاده کرد .

 Crossoverو mutation دو تا عملگر اوليه براي کدگذاري هستند در ادامه بحث به کدگذاري crossover و mutation اشاره مي شود .

سوال بعدي اينکه چگونه والدين  را براي crossover پيدا کنيم اين انتخاب مي تواند به چندين صورت انجام گيرد ولي ما مي خواهيم بهترين والدين را انتخاب کنيم به اميد اينکه بهترين فرزندان به وجود آيد .

توليد نسل فقط از دو کورموزوم نمي تواند جواب چندان مناسبي را به ما بدهد بنابراين  ما از Elitism استفاده مي کنيم و از نسل بهترين ها را انتخاب مي کنيم  (البته به تعداد مناسب ) و بدون هيچ تغييري در نسل بعد کپي مي کنيم بنابراين  بهترين راه حل ها در نسل بعدي  حفظ

 مي شود . واين روند ادامه پيدا مي کند .

http://www.wseas.us/e-library/conferences/2007corfu/papers/540-121.pdf