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

[ravegoat]

تمامي متغير هاي طراحي بايد به صورت يك رشته تعريف شوند. روش GA ايجاب مي كند كه متغير ها مانند يك كروموزوم باشند تا بتوان فرآيند هايي نظير جهش را روي آن ها پياده سازي كرد. عمل تبديل متغير هاي طراحي به رشته را Coding مي گويند. فرضا" اگر متغير طراحي ما طول تير باشد مي توان براي تبديل آن به يك رشته آن مقدار طول را در مبناي عدد 2 بيان كرد. در اين صورت اگر طول تير 3 متر باشد، كروموزوم به شكل زير تعريف مي شود:

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

طول يك كروموزوم بستگي به گستردگي فضاي جست و جو ما دارد. در مثال بالا از 8 بيت استفاده شده است. فرض بر اين بوده است كه طول تير فقط در واحد هاي يك متري تغيير مي كند و در نتيجه اين مدل كدينگ مي تواند تيري با طول صحيحي بين 0 تا 255 متر را پوشش دهد. بديهي است كه براي گستره ي طول بزرگ تر بايد تعداد بيت ها را افزايش داد.

متغير هاي طراحي ما همواره مقادير عددي نيستند. مسئله ي فروشنده ي دوره گرد (Traveling Saleman Problem) در نظر بگيريم. در اين مسئله فروشنده بايد فرضا" از هشت جزيره ي A، B تا H به ترتيبي عبور كند كه حداقل فاصله ي ممكن براي سفر به تمام اين جزيره ها را پيموده باشد. در اين مسئله ترتيب پيمايش جزيره ها، متغير طراحي است و مسافت طي شده، تابع هدف خواهد بود كه مقدار آن بايد كمينه شود. براي كد كردن متغير طراحي مي توان اين ايده را به كار بست:
يك كروموزوم 8 بيتي تعريف مي كنيم كه بيت اول آن از سمت چپ، نام اولين جزيره اي است كه فروشنده به آن سفر مي كند. بيت دوم نام دومين جزيره اي خواهد بود كه فروشنده به آن مي رود و الي آخر. پس كروموزوم زير نشان مي دهد:

B|A|C|E|H|F|D|G

كه فروشنده سفر خود را از جزيره ي B آغاز كرده است. بعد به جزيره ي A رفته است و طبق همين روند، سفر او در جزيره ي G خاتمه يافته است.

همان طور كه ملاحظه مي كنيم روش Coding اختياري و به شكلي قراردادي است و ممكن است براي يك مسئله روش هاي مختلفي براي كدينگ وجود داشته باشد اما هر روش كدينگ حتما" (تاكيد مي شود حتما") بايد دو ويژگي زير را داشته باشد:

1. روش كد كردن بايد تمام فضاي جست و جو ي متغير هاي طراحي را پوشش دهد. از ديد رياضي كد كردن بايد از فضاي جست و جو به فضاي رشته ها پوشا باشد. اگر روشي حتي اگر يكي از حالت هاي فضاي جست و جو را نتواند پوشش دهد، آن روش كدينگ مناسب نخواهد بود. به عنوان مثال اگر روش كد كردن يكي از مقادير طول تير و يا يكي از حالت هاي سفر فروشنده در مثال هاي فوق را نتواند به شكل يك كروموزوم نشان دهد، نمي توان از آن روش كدينگ استفاده كرد.
2. روش كدينگ نبايد دو مقدار و يا دو حالت در فضاي جست و جو را با يك رشته ي يكسان نشان دهد. از ديد رياضي كد كردن بايد از فضاي جست و جو به فضاي رشته ها رفتار تابع را داشته باشد. در مثال فوق اگر روش كد كردن، دو طول مختلف تير را با رشته ي يكساني نمايش دهد، نمي توان از آن روش استفاده كرد.

لازم به ذكر است كه اگر كدينگ براي يك حالت در فضاي جست و جو، دو يا تعداد بيش تري رشته در نظر بگيرد، آن روش همچنان معتبر است. از ديد رياضي روش كدينگ الزما" نبايد يك تابع يك به يك باشد. در مثال فروشنده ي دوره گرد، مسافت طي شده در دو حالت زير با هم برابر اند:

B|A|C|E|H|F|D|G

G|D|F|H|E|C|A|B

به عبارتي يكي حالت مسير رفت و ديگري حالت مسير برگشت را نشان مي دهند.

توجه داشته باشيم كه هرچه روش Coding ساده تر باشد و براي تعريف آن از تعداد كم تري بيت استفاده شود، الگوريتم ژنتيك سريع تر عمل مي كند و عمل Decoding نيز ساده تر خواهد بود.