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

هوائي مركبة الفضاء التابعة لناسا في 2006، ST5. هذا الشكل المعقد عثر عليه برنامج تصميم حاسوبي تطوري لخلق أفضل نمط إشعاع.

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

الخوارزمية الوراثية: هي تقنية بحث تستعمل لإيجاد حلولِ مضبوطة أَو تقريبية التي تحقيقِ الأمثلية، الخوارزميات الوراثية تصنف كبحوث العالمية الاستدلالي(Global search heuristics), وهي أيضا فئة معينة من الخوارزميات التطورية المعروفة كذلك بِالحساب التطوريِ (evolutionary computation) التي تستخدم تكنولوجيا المستوحاة من البيولوجيا التطورية (evolutionary biology) مثل التوريث والطفرات والاختيار والتهجين (crossover).

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

المنهج (Methodology)

الخوارزميات الجينية يتم تنفيذها باعتبارها محاكاة الكمبيوتر حيث تستخدم الكورموسومات كأفراد في العمليات التي تقوم بها لإيجاد افصل الحلول، بشكل عام الحلول تمثل بنظام الثنائي (binary) من 0 و1 ،وأيضا يمكن استخدام رموز أخرى.

عملية التطور(evolution) تبدأ عادة من اختيار الكورموسومات (population) بشكل عشوائي وهذا يحدث في الأجيال الأخرى ،في كل جيل يتم حساب الدالة الأمثلية(fitness function) لكل الكروسومات بشكل منفرد ويتم اختيار أفضل الكورموسومات بالاعتماد على أفضل الدالة الأمثلية ومن ثم عمل تهجين (دمج) وأيضا عمل طفرة، هذه الخوارزمية تتوقف عندما نصل إلى أكبر عدد من الأجيال تم إنتاجه أو الوصل إلى أفضل تحيق من خلال الدالة الأمثلية، إذا كان التوقف بسبب أكبر عدد من الأجيال يكون الحل الأمثل غير متحقق.

الخوارزميات الجينية توجد في التطبيقات المعلوماتية الأحيائية (bioinformatics) وعلوم الحاسوب والهندسة والاقتصاد والكيمياء والصناعات التحويلية (manufacturing) والرياضيات والفيزياء وغيرها من الميادين.


خطوات الخوارزمية الجينية

1. التهيئة(initialization)

في البداية العديد من الحلول الفردية هي مولده عشوائيا على شكل أولي للكورموسومات. حجم الكورموسومات يعتمد على طبيعة المشكلة، ولكن عادة ما يوجد عدة مئات أو آلاف من الحلول الممكنة. بشكل تقليدي يتم تتولد الكورموسومات بشكل عشوائي ،بحيث تغطي مجموعة كاملة من الحلول الممكنة البحث الفضائي(search spaces)وفي بعض الأحيان، فإن هذا الحل قد تكون "المصنف" في حالة الوصول إلى الحل المثل(optimal solution).

2.الاختيار (selection)

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

3. الاستنساخ (reproduction)

هي عملية لتوليد جيل ثان من الكورموسومات التي تم انتقاؤها من خلال عملية الاختيار ومن ثم عمل عميلة التهجين(crossover) والطفرة(mutation)لإنتاج الأبناء.

عملية التهجين

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

توجد العديد من التقنيات التي تَستعمل في عملية التهجين:

  • نقطة تهجين واحدة

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

  • نقطتين تهجين

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

  • القطع والوصل

حيث هذه العملية تعمل على قطع البيانات من منطقة تختلف عن منطقة الكروموسوم الثاني مما يودي إلى اختلاف في طول الكروموسوم.

الطفرة هي عملية تغير مفاجأة في الأبناء الناتجة من عملية التهجين بحيث تكون تغير في شكل الكروموسوم عن طريق تغير أحد مكونات الكروموسوم (تغير bit) هذه العملية ليسن ناتجة من الآباء.

عملية الاستنساخ في النهاية تؤدي إلى إنتاج الكورموسومات جديدة فيتم تطبيق عليها الدالة الأمثلية لإنتاج أبناء جدد.

4. الإنهاء (Termination)

عملية إيجاد جيل جديد تستمر حتى يحدث أحد أسباب الإنهاءو هي:

  1. الوصول إلى الحل الأفضل.
  2. الوصل إلى العدد من الأجيال المطلوب.
  3. الوصول إلى قيمة معينة(budget) مثل حساب (الزمن/المال).
  4. الوصل إلى (local minimum) وعدم المقدرة على الخروج منها.
  5. التخمين.
  6. باستخدام مجموعة من الأسباب السابقة.

5. الشيفرة التضليلية (Pseudo-code) للخوارزمية.

  1. اختيار مجموعة البيانات الكورموسومات(Population).
  2. حساب الدالة الأمثلية لكل كروموسوم.
  3. إعادة
    1. اختيار أفضل آباء لعملية إنتاج الأبناء.
    2. توليد جيل جديد باستخدام التهجين والطفرة.
    3. تقيم للابن الجديد بالاعتماد على الدالة الأمثلية.
    4. عمل تغير للكروموسومات الأصلية بالاعتماد على قيم الأبناء.
  4. أكمل حتى الانتهاء

الإشكال

عادة ما يتم استعمال هذه الطريقة للقيام بالبحث في فضاء بحث (مجموعة عناصر يتم البحث فيها) أو في عملية استمثال ،أي أن الهدف هو جعل دالة رياضية معينة تتخذ قيمة علوى قصوى أو دنيا قصوى ولهذه الدالة اسم خاص في مجال الخوارزميات الجينية حيث يطلق عليها اسم دالة لأمثلية fitness function.

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

مصطلحات الخوارزميات الجينية

رغم أن تطبيق هذه الطريقة عادة يتلخص في عملية استمثال فإنها لها مصطلحاتها الخاصة نظرا لأصولها الراجعة أو المرتبطة بنظرية التطور. من أهم هذه المصطلحات:

  • الإصطفاء: وهي عملية إصطفاء الكروموزومات أي الأفراد أي الحلول التي ستشارك في عملية التكاثر أي التي سيتم عليها لاحقا عملية مزج أجزائها مع أجزاء حلول أخرى أو تغير جزء من أجزاء هذا الحل
  • الفرد أو الكروموزوم: هي الحلول المتاحة والتي يتم معالجتها
  • الجين: هو أصغر جزء من الفرد وأصغر جزء حامل للمعلومة. حيث يتم عادة تشفير متغيرات الدالة التي تخضع للاستمثال لتكون في الشكل الثنائي (صفر وواحد). البت يسمى جين
  • ال population هي مجموع الحلول المتاحة
  • دالة الأمثلية fitness function: هي الدالة التي تعطي نتيجتها احتمال دخول فرد ما في الإصطفاء وتوريث خاصياته. حيث أن الحلول الأمثل تعطى حظا أكبر للدخول في عملية التكاثر وتوريث الخاصيات أو التغيير.
  • دالة التشفير: هي طريقة تشفير الحل أي متغيرات عملية الاستمثال (تشفير ثنائي مثلا لمتغير ينتمي للأعداد الحقيقية)
  • دالة فك التشفير: دالة فك التشفير هي الدالة العكسية لدالة التشفير التي نحتاجها لقرائة الحل النهائي الذي تعطيه الخوارزمية الجينية
  • تلاقح cross over: عملية يتم خلالها تبادل أجزاء حلول (قيمة متغيرات) بين الأفراد أو الصبغيات أو الكروموزومات التي تم اصطفائها سابقا للدخول في هذه العملية
  • mtutation عملية تغير على صبغية معينة أي طفرة أو تغير يطرؤ على إحدى متغيراته

طريقة العمل

تقوم طريقة الخوارزميات الجينية على توليد حلول جديدة تولد حلولا من احتمالات مشفرة على الشكل المعروف ب "كروموسوم" أَو "مورّث". الكروموسومات تجمع أو تتغير لإنتاج الأفراد الجدد. وهي مفيدة لإيجاد الحل الامثل للمعضلات المتعددة الأبعاد التي يمكن فيها أن تشفر القيم للمتغيرات المختلفة فيها على شكل الكروموسوم.

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

فالخوارزمية الوراثية مبنية على أساس تقنية الحلول المثلى تحاكي النشوء الطبيعي وذلك عن طريق تشفير الحلول الممكنة لتمثيلها على شكل سلاسل مشابهة لسلاسل الصبغي، ومن ثم تطبيق بعض العمليات البيولوجية (نسخ، تصالب، طفرة)، والعمليات الصنعية(العكس) لإنتاج الحل الأمثل.

والميزة الأهم في الخوارزمية الوراثية هي طبيعتها التكييفية، والتي تجعلها أقل حاجة لمعرفة المعادلة من أجل حلها.

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

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

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

الحلول الناتجة من التزاوج تدخل هي أيضا تحت الفحص والتنقيح لمعرفة مدى كفاءتها واقترابها من الحل الأمثل، فإن ثبتت كفاءة الحل الجديد فإنه يبقى وإلا يُهمل، وهكذا تتم عمليات التزاوج والانتقاء حتى تصل العملية إما لعدد معين من التكرارات (يقرره مستحدم النظام) أو تصل الحلول الناتجة، أو إحداها إلى نسبة كفاءة، أو نسبة خطأ ضئيلة (يحددها المستخدم أيضا) أو حتى الحل الأفضل.

مسألة التاجر المتجول

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

(Pseudo-code) مسألة البائع المتجول

مسألة 8-ملكات (8queens problem)

تتوزع الملكات بشكل عشوائي حيث تمثل مجموعة الملكات بمجموعة أرقام {1،2،3،4،5،6،7،8} حيث يعبر العنصر الأول عن موقع أول ملكه في أول عمود، العنصر الثاني يعبر عن موقع العنصر الثاني في العمود الثاني...... وهكذا. المطلوب توزيع الملكات بحيث لا تتواجد ملكتين في نفس الصف أو العمود أو القطر الصورة التالية تظهر المطلوب.

طريقة العمل

تقوم الخوارزمية الوراثية باختيار أفضل الكورموسومات باستخدام الدالة الأمثلية من مجموعة الكورموسومات الأولية الدالة الأمثلية : تكون أعلى درجة (max) =28 (7+6+5+4+3+2+1) اقل درجة =0 حيث 7 تعني أن 8 ملوك في نفس السطر (من اليسار ال اليمن) وهكذا.

فإذا كانت الكورموسومات الأولية هكذا :

الدالة الأمثلية=28-4 =24

الدالة الأمثلية=28-5 =23

الدالة الأمثلية=28-8 =20

الدالة الأمثلية=28-17 =11

اختير أعلى دالة الأمثلية

24/(24+23+20+11) = 31%

23/(24+23+20+11) = 29%

20/(24+23+20+11) = 26%

11/(24+23+20+11) = 11%

يتم اخيار أعلى درجتين من الدالة الأمثلية ومن ثم عمل التهجين والطفرة

تستمر هذه العملية حتى الوصول إلى ان لا تتواجد ملكتين في نفس الصف أو العمود أو القطر.

الاستخدامات


. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

الهامش

  1. ^ Gondro C, Kinghorn BP (2007). "A simple genetic algorithm for multiple sequence alignment". Genetics and Molecular Research. 6: 964–982. PMID 18058716.
  2. ^ van Batenburg FH, Gultyaev AP, Pleij CW (1995). "An APL-programmed genetic algorithm for the prediction of RNA secondary structure". Journal of Theoretical Biology. 174: 269–280. doi:10.1006/jtbi.1995.0098. PMID 7545258.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  3. ^ Notredame C, Higgins DG (1995). "SAGA a Genetic Algorithm for Multiple Sequence Alignment". Nulceic Acids Research. 174: 1515. PMID 8628686.
  4. ^ Cedric Notredame Home Page
  5. ^ Hill T, Lundgren A, Fredriksson R, Schiöth HB (2005). "Genetic algorithm for large-scale maximum parsimony phylogenetic analysis of proteins". Biochimica et Biophysica Acta. 1725: 19–29. PMID 15990235.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  6. ^ Joachim De Zutter
  7. ^ Li, Y., et al. (2004). CAutoCSD - Evolutionary search and optimisation enabled computer automated control system design. International Journal of Automation and Computing, 1(1). pp.76-88. ISSN 1751-8520, http://eprints.gla.ac.uk/3818/
  8. ^ Ng, K.C., Switching Control Systems and Their Design Automation via Genetic Algorithms, PhD Thesis, University of Glasgow, 1995.
  9. ^ Li, Y., et al. (1996). Genetic algorithm automated approach to design of sliding mode control systems, Int J Control, 63(4), 721-739.
  10. ^ Optimised Configuration of Sensing Elements for Control and Fault Tolerance Applied to an Electro-Magnetic Suspension, PhD Thesis, 2009.
  11. ^ SymbioticSphere - Distributed Software Systems Group, University of Massachusetts, Boston
  12. ^ To CC, Vohradsky J (2007). "A parallel genetic algorithm for single class pattern classification and its application for gene expression profiling in Streptomyces coelicolor". BMC Genomics. 8: 49. doi:10.1186/1471-2164-8-49. PMID 17298664.{{cite journal}}: CS1 maint: unflagged free DOI (link)
  13. ^ Hitoshi Iba, Sumitaka Akiba, Tetsuya Higuchi, Taisuke Sato: BUGS: A Bug-Based Search Strategy using Genetic Algorithms. PPSN 1992:
  14. ^ Ibrahim, W. and Amer, H.: An Adaptive Genetic Algorithm for VLSI Test Vector Selection
  15. ^ Bagchi Tapan P (1999). "Multiobjective Scheduling by Genetic Algorithms". {{cite journal}}: Cite journal requires |journal= (help); Text "Kluwer Academic. ISBN 0-7923-8561-6" ignored (help)
  16. ^ Applying Genetic Algorithms to Recurrent Neural Networks for Learning Network Parameters and Architecture
  17. ^ Wang S, Wang Y, Du W, Sun F, Wang X, Zhou C, Liang Y (2007). "A multi-approaches-guided genetic algorithm with application to operon prediction". Artificial Intelligence in Medicine. 41: 151–159. doi:10.1016/j.artmed.2007.07.010. PMID 17869072.{{cite journal}}: CS1 maint: multiple names: authors list (link)
  18. ^ BBC News | Entertainment | To the beat of the byte
  19. ^ Zhang, J., Lo, W.L., and Chung, H., "Pseudocoevolutionary Genetic Algorithms for Power Electronic Circuits Optimization", IEEE Trans Systems, Man, and Cybernetics, Part C., Vol.36, No.4, July 2006, pp.590-598.
  20. ^ Willett P (1995). "Genetic algorithms in molecular recognition and design". Trends in Biotechnology. 13: 516–521. doi:10.1016/S0167-7799(00)89015-0. PMID 8595137.
  21. ^ BiSNET/e - Distributed Software Systems Group, University of Massachusetts, Boston

ببليوجرافيا

  • Banzhaf, Wolfgang; Nordin, Peter; Keller, Robert; Francone, Frank (1998) Genetic Programming - An Introduction, Morgan Kaufmann, San Francisco, CA.
  • Bies, Robert R (2006). "A Genetic Algorithm-Based, Hybrid Machine Learning Approach to Model Selection". Journal of Pharmacokinetics and Pharmacodynamics. Netherlands: Springer: 196–221. {{cite journal}}: Unknown parameter |coauthors= ignored (|author= suggested) (help)
  • Cha, Sung-Hyuk (2009). "A Genetic Algorithm for Constructing Compact Binary Decision Trees". Journal of Pattern Recognition Research. 4 (1): 1–13. {{cite journal}}: External link in |journal= and |title= (help); Unknown parameter |coauthors= ignored (|author= suggested) (help)
  • Fraser, Alex S. (1957). "Simulation of Genetic Systems by Automatic Digital Computers. I. Introduction". Australian Journal of Biological Sciences. 10: 484–491.
  • Goldberg, David E (1989), Genetic Algorithms in Search, Optimization and Machine Learning, Kluwer Academic Publishers, Boston, MA.
  • Goldberg, David E (2002), The Design of Innovation: Lessons from and for Competent Genetic Algorithms, Addison-Wesley, Reading, MA.
  • Fogel, David B (2006), Evolutionary Computation: Toward a New Philosophy of Machine Intelligence, IEEE Press, Piscataway, NJ. Third Edition
  • Holland, John H (1975), Adaptation in Natural and Artificial Systems, University of Michigan Press, Ann Arbor
  • Koza, John (1992), Genetic Programming: On the Programming of Computers by Means of Natural Selection, MIT Press. ISBN 0-262-11170-5
  • Michalewicz, Zbigniew (1999), Genetic Algorithms + Data Structures = Evolution Programs, Springer-Verlag.
  • Mitchell, Melanie, (1996), An Introduction to Genetic Algorithms, MIT Press, Cambridge, MA.
  • Poli, R., Langdon, W. B., McPhee, N. F. (2008). A Field Guide to Genetic Programming. Lulu.com, freely available from the internet. ISBN 978-1-4092-0073-4.{{cite book}}: CS1 maint: multiple names: authors list (link)
  • Rechenberg, Ingo (1994): Evolutionsstrategie '94, Stuttgart: Fromman-Holzboog.
  • Schmitt, Lothar M; Nehaniv, Chrystopher L; Fujii, Robert H (1998), Linear analysis of genetic algorithms, Theoretical Computer Science 208: 111-148
  • Schmitt, Lothar M (2001), Theory of Genetic Algorithms, Theoretical Computer Science 259: 1-61
  • Schmitt, Lothar M (2004), Theory of Genetic Algorithms II: models for genetic operators over the string-tensor representation of populations and convergence to global optima for arbitrary fitness function under scaling, Theoretical Computer Science 310: 181-231
  • Schwefel, Hans-Paul (1974): Numerische Optimierung von Computer-Modellen (PhD thesis). Reprinted by Birkhäuser (1977).
  • Vose, Michael D (1999), The Simple Genetic Algorithm: Foundations and Theory, MIT Press, Cambridge, MA.
  • Whitley, D. (1994). A genetic algorithm tutorial. Statistics and Computing 4, 65–85.
  • Hingston,Philip F.; Barone,Luigi C.; Michalewicz, Zbigniew (2008) Design by Evolution: Advances in Evolutionary Design:297
  • Eiben,Agoston E.; Smith, James E. (2003) Introduction to Evolutionary Computing

وصلات خارجية

بدليل لبناء صناديق افتراضية

  • Generative Fixation A unified explanation for the adaptive capacity of simple recombinative genetic algorithms

مصادر

دروس تدريبية

تمّ الاسترجاع من "https://www.marefa.org/w/index.php?title=خوارزميات_وراثية&oldid=1713466"