الخوارزميات الجينية (الحلقة 4 والأخيرة)Genetic Algorithm

facebook-group

بسم الله الرحمن الرحيم

السلام عليكم ورحمة الله وبركاته

أخواتي إخواني الأعزاء , عذراً في حال كنت قد أطلت عليكم ريثما قمت بإعداد هذه الحلقة من سلسلة الخوارزميات الجينية , لنتابع سوية ما قد بدأنا به مسبقاً.

 بعد أن وصلنا إلى ما وصلنا إليه في الحلقات السابقة , وأصبح لدنيا الآن دراية واسعة في معنى  الخوارزميات الجينية ,وبعد أن أحطنا بكم كافي من المعلومات المتعلقة بالمكونات الأساسية للخوارزميات الجينية , والعمليات الأساسية التي تجرى عليها , أصبح الآن بإمكاننا التطرق لمبدأ الخوارزميات الجينية , حتى تصبح مادتنا قابلة للتطبيق العملي والبرمجة , وكما أننا سنستعرض في هذه الحلقة أهمية كل من عمليتي التصالب والطفرة اللتان تتمان على الخوارزميات الجينية ,وذلك عبر بعض الأمثلة العملية .

كما أننا سنتطرق إلى بعض المجالات التي تكون فيها الخوارزميات الجينية مفيدة وفعالة ,وبعض مجالات تطبيقها …

وسأدعكم الآن لتستمتعوا بمحتويات هذه الحلقة الأخيرة من الخوارزميات الجينية بشكل مفصل…

مبدأ الخوارزميات الجينية: [1]

مما سبق نرى بأن مبدأ الخوارزميات الجينية بسيط جداً ويمكن تلخيصه كما يلي :

1: ترميز المسألة بالشكل المناسب والأمثل

2:التوليد العشوائي للتجمعpopulation  البدائي المؤلف من مجموعة من الكروموزومات التي تتألف بدورها من مجموعة من الجينات , حيث ان كل كروموزوم (الذي هو عبارة عن تجمع جيني) عبارة عن حل.

3:حساب قيمة الصلاحية لكل كروموزوم (حل) من الكروموزومات الموجودة في التجمع . ويعتمد أسلوب تقييم  صلاحية كل حل في الجيل بمقدار بعده عن الحل الامثلي الذي نبحث عنه.

4:يتم اختيار الكروموزومات التي ستخضع لعملية التصالب لتوليد الجيل الجديد, وعملية الاختيار تقوم بحسب إحدى النظريات الكثيرة المقترحة في هذا المجال,وترتكز عملية الاختيار بشكل اساسي على مدى صلاحية الحل في الانتقال للجيل الثاني والتي يقوم بتحديدها تابع الصلاحية

5:تلي عملية الاختيار , عمليتي التصالب والطفرة .

6: ومن ثم نعود مجدداً للبدء من الخطوة رقم 3.

 

أهمية عمليتي التصالب والطفرة في الخوارزميات الجينية:

تشكل عملية التصالب في الخوارزميات الجينية العملية الأساسية , طبعاً لا غنى لنا عن بقية العمليات مثل الطفرة –التي تعطي نتوع وراثي للتجمع-, في الواقع , قد لا يتواجد الحل المطلوب حتى في تجمع كبير جداً في حال اعتمدنا بشكل اساسي على التصالب فقط , لذلك نحن بحاجة ماسة للطفرة التي تحسن وتزيد فرصة الحصول على الحل الأمثلي , وبالمثل , لا يمكننا الاعتماد على الطفرة وحدها في الخوارزميات الجينية لأنها تبطئ العملية كثيراً , لذلك نلجأ لمزيج من العمليتين بهدف الحصول على الحل الأمثلي –او القريب منه- بأسرع وقت ممكن .

 وحتى لا يبقى الكلام السابق مجرد كلام نظري ,إليكم المثال التالي الذي يوضح أهمية الطفرة والتصالب في الخوارزميات الجينية .

لنتخيل المسألة التالية :

بفرض أن هدفنا هو الحصول على أكبر عدد صحيح موجب ممثل على 7 خانات ثنائية , وذلك انطلاقاً من تجمع يحوي عدد من الكروموزومات –في تمثيلنا للمسألة سلاسل من الخانات الثنائية – المهيئة بشكل عشوائي في بداية التجمع .

(ملاحظة :

بهدف التبسيط , والتركيز على الفكرة المراد إيصالها سنهمل فكرة إشارة العدد الصحيح وأية اعتبارات أخرى.)

 

وضوحاً فإن الحل الأمثل هو السلسلة الثنائية الكاملة الوحدان , اي المؤلفة من تتالي 7 واحد دون ورود أي صفر

1111111

Chromosome  

 

وبفرض أنه بعد عملية التهيئة العشوائية للحلول كان لدينا مجموعة الحلول التالية :

 

Chromosome A

1100011

Chromosome B

0001100

Chromosome C

0110000

 

نجد أن الحل الأمثلي الذي نبحث عنه موجود ضمن التجمع , ولكنه غير فعال لكونه مبعثر ضمن عدد من الحلول , فنجد أنفسنا هنا بحاجة لآلية التصالب crossover  بهدف دمج هذه الحلول معاُ والوصول للحل المطلوب

, وبفرض أن الخوارزمية المتبعة هنا تعتمد بشكل أساسي على عملية التصالب فقط , دون عملية الطفرة , وبعد عدد معين من الأجيال وصلنا لحلول مقاربة جداً للحل الأمثلي , سلاسل مفعمة بالوحدان , ولكن للصدفة السعيدة , فإن أي من هذه السلاسل لا يحوي الواحد في الخانة الأولى , وبالتالي وبالاعتماد على التصالب فقط , قد نصل لحل قريب جداً من الحل الأمثلي

Chromosome X

1111110

 

 

لكننا لن نصل بحياتنا للحل الأمثلي نهائياً , وذلك لافتقارنا لعملية الطفرة التي قد تغير مجرى العملية كلها إذا حدث وأن قلبت أول صفر لواحد في أحد الحلول , وعندها تعود لنا فرصة الحصول على الحل الأمثلي.

 

وسنستغل فرصة ذكر المثال السابق بهدف توضيح مفهومي الجينوتايب , والفينوتايب, نستذكر حديثنا عن هذين المفهومين من المقدمة البيولوجية , حيث إن الجينوتايب يمثل الحل بشكله الوراثي , وبالقياس نجد أن الجينوتايب في المسألة السابقة يمثل السلسلة الثنائية ذات السبع خانات المتتالية من الأصفاروالوحدان , بينما الفينوتايب يمثل الحل بشكله الفيزيائي , أي في مسألتنا يمثل القيمة العددية الصحيحة للحل الناتج .

 

الرسم :

 

 

 

متى تكون الخوارزميات الجينية مفيدة وفعالة : [3]

تكون بشكل عام الخورازميات الجينية مفيدة وفعالة في أحد الحالات التالية :

  1: عندما يكون فضاء البحث كبير جداً و معقد إلى حدٍ ما وغير مفهوم بشكل واضح

 2: المعلومات ,أو بالاحرى المعرفة في المجال المدروس نادرة , أو أنه من الصعب ترميز خبرة الخبير في المجال المدروس بهدف تضيّق فضاء البحث

3:لا يوجد طرائق تحليل رياضي معروفة لحل المسألة .

4: فشلت طرائق البحث التقليدية لحل المسألة .

 

مجالات تطبيق الخوارزميات الجينية : [1]

تم تطبيق الخوارزميات الجينية في عدد كبير من المجالات , منها العلمية , المسائل الهندسية , وفي مجال الأعمال والألعاب و الروبوتات …

بعض التصنيفات الرئيسية التي استخدمت فيها الخوارزميات الجينية :

1:مسائل الأمثلة بشكل عام :

بما فيها الأمثلة العددية , والحسابية مثل مسألة البائع المتجول TSP  ,التصميم الصناعي مثل مسألة آلة تقطيع الخشب ,جدولة أعمال التسوق , أمثلة جودة الصوت والفيديو.

2: البرمجة الاوتوماتيكية :

حيث تم استخدام الخوارزميات الجينية لتطوير برامج حاسوبية بهدف تنفيذ مهام محددة ,ولتصميم بنى حاسوبية أخرى ,مثل شبكات الفرز sorting network  .

3:تعليم الروبوتات والآلات :

تم استخدام الخوارزميات الجينية في كثير من تطبيقات التعلم التلقائي machine –learning  ,ومن ضمنها التصنيف classification  و النتبأ prediction  .

وقد تم استخدام الخوارزميات الجينية في تصميم الشبكات العصبونية neural networks design  .

 

4:النماذج الاقتصادية Economic models

تم استخدام الخوارزميات الجينية لنمذجة آليات ابتكار وتطوير استراتيجيات المزايدة .وفي مجال نشوء الأسواق الاقتصادية emergence of economic markets .

5: التفاعل بين التطور والتعلم :

حيث تم استخدامها لدراسية التأثير المتبادل بين تعلم الأفراد وتطور الأنواع .

6:كنماذج للأنظمة الاجتماعية :

تم استخدامها لدراسة جوانب تطور النظم الاجتماعية , مثل تطور التعاون evolution of cooperation  و تتطور الاتصال evolution of communication  ,سلوك القافلة لدى النمل trail-following behavior in ants .

والكثير الكثير من المجالات التي استخدمت فيها الخوارزميات الجينية .

 مما سبق تر بأن الخوارزميات الجينية ما هي إلا طريقة ذكية لحل طيف واسع من المسائل ,بعضها لم يجد له حلاً ممكناً أو فعالاً بالطرق التقليدية , ولكننا بالوقت نفسه لا نستطيع القول بأنها طريقة إيجابية بشكل مطلق في الحل , فهي مثلها مثل بقية الخوارزميات , لها ايجابياتها وسلبياتها , إيجابياتها من حيث كونها سهلة النتجيز , وأقل عرضة لأن تقع في نهاية محلية , ومن سلبياتها كونها مكلفة حسابياً بشكل عام ,وأبطأ من بعض الطرائق الأخرى , وعلى كل الأحوال , فإنه مع الامكانيات الرهيبة للحواسيب الحالية , فإن السلبيات السابقة لم تعد بتلك الأهمية الكبيرة.

 وقي النهاية لا يسعنا إلا القول بأن المعلومات السابقة عن الخوارزميات الجينية ما هي إلا قطرة من فيض هائل لا يزال يتطور كل يوم ,ولا يمكننا الاحاطة بها كلها في مقالة واحدة ,ولمزيد من المعلومات يمكن العودة للروابط المذكورة ضمن المراجع.

مراجع للاستزادة

Introduction to Genetic Algorithm

http://www.rennard.org/alife/english/gavintrgb.html

[1]

Introduction to Genetic Algorithm

://cs.felk.cvut.cz/~xobitko/ga

[2]

Genetic Algorithms

http://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol4/tcw2/report.html

[3]

//lancet.mit.edu/~mbwall/presentations/IntroToGAs

[4]

Genetic Algorithms and Evolutionary Computation

http://www.talkorigins.org/faqs/genalg/genalg.html

[5]

 

وعند هذه النقطة , أتمنى أن أكون قد قدمت مافيه الفائدة للأشخاص الذين يهمهم البحث في هذه المجال , أو الأشخاص الباحثين عن كل ما هو جديد في عالم التقنيات المتسارع.

وأتمنى أن أكون قد وصلت معكم ضمن هذه السلسلة إلى نقطة يسعكم معها القيام ببعض التطبيقات العملية البرمجية على الخوارزميات الجينية لتروا بأم أعينكم مفعولها الرائع , ونحن بانتظار تعليقاتكم الكريمة والتغذية الراجعة منكم في هذا السياق.

وأدعوا من الله أن يوفق كل من قام بقراءة هذه الحلقات , ولا يسعني الآن إلا أن أودعكم في ختام هذه الحلقة الأخيرة من سلسلة الخوارزميات الجينية ,آملاً لكم التوفيق .

وإلى لقاء قريب بإذن الله تعالى ,وإلى ذلك الحين أستودعكم الله والسلام عليكم ورحمة الله وبركاته .

فهرس سلسلة الخوارزميات الجينية :

  1. الخوارزميات الجينية ( الحلقة الأولى)
  2. الخوارزميات الجينية ( الحلقة الثانية)
  3. الخوارزميات الجينية ( الحلقة الثالثة)
  4. الخوارزميات الجينية ( الحلقة الرابعة والأخيرة)
Advertisements

, , , , , ,

  1. #1 by jehazee on مارس 23, 2009 - 8:32 م

    اشكرك عزيزي وباذن الله تعالى ساقوم بقاة الدروس من البدايه

    وشكراً لك

    • #2 by schwarztiger on أبريل 3, 2009 - 2:01 م

      السلام عليكم ورحمة الله وبركاته
      وفقك الله , ونور عقلك وقلبك بالعلم والإيمان

  2. #3 by مهند on يوليو 13, 2009 - 11:42 ص

    أرجو الاستفسار عن كيفية استخدام الخوارزميات الجينية في محركات البحث؟ وبخاصة في عملية الترتيب Ranking

    • #4 by schwarztiger on يوليو 16, 2009 - 11:09 ص

      السلام عليكم ورحمة الله وبركاته
      الزميل مهند المحترم , استفسارك عام لدرجة أنه يحتاج لتحديد أكثر حتى استطيع الإجابة عليه بدقة
      حيث يمكن استخدام الخوارزميات الجينية في عدة تطبيقات , فمثلا في مجال محركات البحث , بإمكانك كمبرمج استخدام الخورازميات الجينية في تحديد التوزع الأمثل للروابط ضمن موقعك التي تعطيك PR الأفضل وذلك بالاستفادة من تابع ال fitness المستخدم بالخورازميات الجينية .
      هذه هي احد الاستخدامات الممكنة للخورازميات الجينية في مجال محركات البحث و رفع PR الموقع ضمن النتائج المحتملة للبحث , طبعاً النقاش هنا يحتمل الكثير من التفصيل والدراسة المعمقة , ولكن ببساطة تلك كانت هي فكرته الاساسية
      والسلام عليكم

  3. #5 by Sulaiman on يوليو 29, 2009 - 4:03 م

    مشكور اخي وبارك الله فيك

    حقيقة انا الان سوف اقدم بحث في ال Genetic algorithms وقد افدتني كثيرا

    شكرا جزيلا

    سليمان

    • #6 by schwarztiger on يوليو 30, 2009 - 7:11 ص

      السلام عليكم ورحمة الله وبركاته
      اخي المحترم سليمان
      اتمنى لك التوفيق من كل قلبي في البحث الذي تقدمه في الخورازميات الجينية
      وأنا في غاية السرور لأنني استطعت أن افيدك بشكل أو بأخر

  4. #7 by محمد سلمان on أغسطس 3, 2009 - 7:46 ص

    السلام عليكم وجزاكم الله كل خير على مجهودكم هل يمكن ان تفضل علينا باخذ مثال متكامل ومن ثم تبدا بحله لتوضيح اكثر مع فائق شكري وتقديري

  5. #8 by فيصل on يوليو 28, 2010 - 2:03 ص

    بارك الله فيك عزبزى كاتب هده الحلقات, وارجو التواصل لان هده المعلومات قد يصعب قرائتها باللغة الانجليزية, وفقك الله .

    • #9 by schwarztiger on يوليو 28, 2010 - 9:03 ص

      السلام عليكم ورحمة الله وبركاته
      الأخ فيصل ,مشكور على مرورك الكريم ودعائك لنا بالتوفيق , على فكرة قمت بتحويل كافة محتويات الموقع الحالي إلى موقع ثاني أوسع في مجال المعطيات المطروحة , قمت ببرمجته بنفسي , لذلك فإن أي مواضيع لاحقة سأقوم بترجمتها وتنزيلها ستجدها على الموقع التالي
      http://www.mathaheb.com
      وإذا كان لديك أي اقتراحات لمواضيع علمية بحاجة فعلية للترجمة للغة العربية أرجو الإشارة إليها حتى نقوم بدراستها بشكل معمق وترجمتها ومنقشتها سوياً حتى تعم الفائدة للجميع
      والسلام عليكم

  6. #10 by Mohammed Alhadad on مارس 30, 2013 - 9:57 م

    السلام عليكم ورحمة الله وبركاته
    شكرا لك بش مهندس على الطرح الاكثر من رائع فلقد قرات الحلقات كلها وتكونت لدي الفكرة والفائده.
    وارجو منك ومن الاعزاء الذين لهم خبرة في هذا المجال(الخورزميات الجينية والشبكات العصبية)ان يفيدوني في كيفية تطبيق هذه الخوارزميات على اشارة تخطيط القلب لتصنيفها(arrhythmias classification using genetic algorithm and support vector machine)واكون شاكرا لكم ودمتم….
    وهذا ايميليalhadad13@yahoo.com
    وايضا حسابي في الفيس بوك https://www.facebook.com/mohammed.alhadad3?ref=tn_tnmn
    ولكم خالص شكري وتقديري

  7. #12 by Mohammed Alhadad on يونيو 9, 2013 - 2:43 ص

    السلام عليكم
    ممكن مثال تطبيقي على الخوارزمية الجينية (حسابيا وبرمجيا)
    حتى ولوكان بسيط

  8. #13 by hope (@hope10564619) on سبتمبر 19, 2013 - 5:16 م

    بارك الله فيك و جزاك الله كل خير
    و لي عودة بعدة اسىلة ان شاء الله

اترك رد

Please log in using one of these methods to post your comment:

WordPress.com Logo

أنت تعلق بإستخدام حساب WordPress.com. تسجيل خروج   / تغيير )

صورة تويتر

أنت تعلق بإستخدام حساب Twitter. تسجيل خروج   / تغيير )

Facebook photo

أنت تعلق بإستخدام حساب Facebook. تسجيل خروج   / تغيير )

Google+ photo

أنت تعلق بإستخدام حساب Google+. تسجيل خروج   / تغيير )

Connecting to %s

%d مدونون معجبون بهذه: