الگوريتم ژنتيك (GA)

[ravegoat]

زادولد (Crossover)
عملي است كه از تركيب دو كروموزوم به عنوان والدين (Parents)؛ دو كروموزوم جديد به عنوان فرزند (Offspring) به وجود مي آورد. فرزندان بخشي از اطلاعات مادر و بخشي از اطلاعات پدر را به ارث مي برند. گونه هاي متداول توليد مثل به شكل زير است:

1. One-point Crossover
2. Two-point Crossover
3. Scattering Crossover

One-point Crossover
در اين روش كرموزوم مادر از يك نقطه ي مشخص به دو بخش تقسيم مي شود. كروموزوم پدر نيز از همان نقطه ي مشخص به دو بخش تقسيم مي شود. حال فرزند اول از اتصال بخش اول كروموزوم مادر و بخش دوم كروموزوم پدر متولد مي شود. فرزند دوم نيز از اتصال بخش اول كرموزوم پدر و بخش دوم كرموزوم مادر به وجود مي آيد. محل برش بايد به شكل تصادفي تعيين شود.

1|1|0|0|1|1|0|1 مادر

0|1|0|1|0|1|0|1 فرزند اول

1|1|0|0|1|1|0|0 فرزند دوم

0|1|0|1|0|1|0|0 پدر

Two-point Crossover
در اين روش كرموزوم مادر از دو نقطه ي مشخص به سه بخش تقسيم مي شود. كروموزوم پدر نيز از همان دو نقطه ي مشخص به سه بخش تقسيم مي شود. حال فرزند اول از اتصال بخش اول كروموزوم مادر ، بخش دوم كروموزوم پدر و بخش سوم كروموزوم مادر متولد مي شود. فرزند دوم نيز از اتصال بخش اول كروموزوم پدر ، بخش دوم كروموزوم مادر و بخش سوم كروموزوم پدر به وجود مي آيد. محل نقاط برش همچنان بايد به شكل تصادفي تعيين شود.

1|1|0|0|1|1|0|1 مادر

1|1|0|1|0|1|0|1 فرزند اول

0|1|0|0|1|1|0|0 فرزند دوم

0|1|0|1|0|1|0|0 پدر

Scattering Crossover
در اين روش ابتدا يك رشته ي باينري متشكل از صفر و يا يك هاي تصادفي به طول كرموزوم هاي جمعيت توليد مي شود. حال اگر بيت اول رشته ي باينري توليد شده يك باشد، بيت اول كروموزوم مادر و بيت اول كروموزوم پدر جاي خود را با يكديگر عوض مي كنند. ولي اگر بيت اول رشته ي باينري صفر باشد، اين جايگزيني صورت نمي گيرد. همين روند براي بيت هاي بعدي نيز تكرار مي شود. در نهايت مادر و پدر با جايگزيني بيت هاي خود طبق الگوي رشته ي باينري، دو فرزند به وجود مي آورند.

مادر:

A|C|D|A|B|C

پدر:

B|A|B|C|D|A

رشته ي باينري توليد شده به شكل تصادفي:

0|1|0|0|1|1

فرزند اول:

B|A|D|A|D|C

فرزند دوم:

A|C|B|C|B|A

جهش (Mutation)
عملي است كه يك بيت كروموزوم را به شكل تصادفي انتخاب كرده و مقدار آن را تغيير مي دهد:

0|1|1|0|0|0|1|1

<< جهش

0|1|1|0|1|0|1|1