هندسة الكهرباء والإلكترونيات هندسة وتكنولوجيا

الخوارزميات الوراثية ومحاكاة الحاسوب لنظرية التطور

الخوارزميات الوراثية ومحاكاة الحاسوب لنظرية التطور

الخوارزميات الوراثية (Genetic Algorithms) هي جزء من مجموعة أكبر من الخوارزميات تسمى الخوارزميات التطورية (Evolutionary Algorithms). استخدم علماء الحاسوب نظرية التطور لداروين، ومصطلح «البقاء للأفضل»، في بناء hنظمة برمجية قادرة على إيجاد الحل الأفضل لمشكلة معينة ما بين مجموعة كبيرة من الحلول، وذلك عن طريق تطور هذه الحلول من جيل إلى جيل، وكل جيل يتطور ليصبح أفضل من الجيل السابق له. يستخدم علماء الحاسب نظرية التطور للإلهام فقط، وليس شرطًا أن يبنوا أنظمة وخوارزميات تستخدم نظرية التطور كما هي في علم الأحياء، بل لهم الحرية في أخذ ما يفيدهم وما يريدونه وترك ما لا يفيدهم وما لا يريدونه. وفي الصورة التالية يوجد تصميم لهوائي (Antenna)، تم إنتاج هذا التصميم في شركة ناسا (NASA) عن طريق برنامج للحاسوب يستخدم الخوارزميات الجينية.(1)

220px-st_5-xband-antenna

طريقة عمل الخوارزمية الوراثية

طريقة عمل الخوارزميات الوراثية مستوحاة من العمليات التي تحدث أثناء عملية التطور في الكائنات الحية، وهذه العمليات هي الانتخاب الطبيعي (Natural Selection) والوراثة (Inheritance) والخلط (Crossover) والتبديل أو الطفرة (Mutation)، والخوارزميات الوراثية هي عبارة عن نظام برمجي حيث هناك مجموعة من الحلول (Population) لمشكلة معينة، تتطور وتتقدم لتصبح أفضل. تبدأ عملية التطور من مجموعة عشوائية من الأفراد (الحلول) وتحدث عملية التطور على مستوى أجيال (generations)، في كل جيل يتم حساب كفاءة كل فرد في هذا الجيل، ثم يتم اختيار مجموعة من الأفراد من الجيل الحالي بناءً على كفاءتهم، هؤلاء الأفراد يتم تعديلهم وإحداث الطفرة فيهم وخلطهم لإنتاج جيل جديد والذي يتم تكرار نفس العمليات السابق ذكرها عليه وهكذا. عادة يكون شكل كل حل من الحلول عبارة عن سلسلة مكونة من رقمين الصفر والواحد، مثال: (10101100)، وتسمى هذه السلسلة كروموسوم (Chromosome) ويسمى كل رقم في السلسلة جين (Gene)، ومع ذلك يمكن أن يتم تحويله إلى شكل مختلف على حسب نوع المشكلة التي تقوم الخوارزمية بحلها. وعملية الخلط (Crossover) تكون عبارة عن أخذ حلين من الحلول وخلطهم لإنتاج حلين مختلفين، مثال: لنفرض أن لدينا حل هو (10101100) ولدينا حل آخر هو (11110000)، تتم عملية الخلط عن طريق أخذ النصف الأول من الحل الأول وهو (1100)، وأخذ النصف الثاني من الحل الثاني وهو (1111)، ثم إنتاج حل جديد مكون من هذين النصفين وهو (11111100)، وبهذا الشكل يحتوي الكروموسوم للحل الجديد علي جينات من كلا الكروموسومين للحلين القديمين. أما عملية التبديل أو الطفرة فتتم عن طريق تبديل أحد الأرقام الموجودة في الحل (تبديل أحد الجينات الموجودة في الكروموسوم)، مثال: لنفرض أن لدينا حل وهو (10110010)، فإن عملية الطفرة ممكن أن تُبدل أول رقم من اليمين وهو الصفر وتحوله إلى واحد، فيصبح شكل الحل الجديد كالتالي (10110011).(2)

flow

تاريخ الخوارزميات الوراثية

بدأ العمل على ما يسمى هذه الأيام بالخوارزميات التطورية (Evolutionary Algorithms) في ستينيات القرن الماضي، وتحديدًا في الولايات المتحدة وأوربا. كان جون هولاند (John Holland) وزملائه في جامعة ميتشيجان (Michigan) مهتمين بأنظمة الذكاء الاصطناعي القادرة على التأقلم تحت الظروف البيئية المتغيرة. وكانت هذه هي الفكرة، أنه لكي تتمكن مجموعة من الأفراد من التأقلم في بيئة معينة، فإنها يجب أن تَعمل كما يعمل النظام الطبيعي، حيث يتم حذف الحلول عديمي الفائدة ومكافئة الحلول ذات الفائدة. وكانت رؤية جون هولاند هي بناء خوارزميات وراثية تمتلك خصائص التطور الطبيعي، وتحويل هذه الخصائص إلى شكل يمكن معالجته رياضيًا، ثم استخدام تلك الخوارزميات وتطبيقها في حل الكثير من المشكلات الموجودة في الواقع.(3)

 

إعداد وتصميم: Osama Ahmed
مُراجعة ونشر وتحرير: Mehmed Shaalan

المصادر:

G.S. Hornby, A. Globus, D.S. Linden, J.D. Lohn, Automated antenna design with evolutionary [1] algorithms, in: Proceedings of 2006 American Institute of Aeronautics and Astronautics Conference on Space, San Jose, CA, 2006, pp. 19–21.
Aljuaid, Hanan. Applying Genetic Algorithm in Multi Language’s Characters Recognition. INTECH [2] Open Access Publisher, 2012.‏
M. Tomassini. A Survey of Genetic Algorithms. Annual Reviews of Computational [3] Physics, 3:87 118, 1995.