الخوارزمية الجينية 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 حيثسبعة تعني حتىثمانية ملوك في نفس السطر (من اليسار ال اليمن) إلى غير ذلك.

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

الدالة الأمثلية=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%

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

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

الاستخدامات

• Artificial creativity
• Audio watermark detection
• Automated design = Computer-automated design
• Automated design of mechatronic systems using bond graphs and genetic programming (NSF).
• Automated design of industrial equipment using catalogs of exemplar lever patterns.
• Automated design of sophisticated trading systems in the financial sector.
• Automated design, including research on composite material design and multi-objective design of automotive components for crashworthiness, weight savings, and other characteristics.
• Bioinformatics Multiple sequence alignment.
• Bioinformatics: RNA structure prediction.
• Bioinformatics: [Multiple Sequence Alignment]. SAGA is available on: .
• Building phylogenetic trees.
• Calculation of bound states and local-density approximations.
• Chemical kinetics (gas and solid phases)
• Code-breaking, using the GA to search large solution spaces of ciphers for the one correct decryption.
• Computer-automated design
• Configuration applications, particularly physics applications of optimal molecule configurations for particular systems like C60 (buckyballs).
• Container loading optimization.
• Control engineering ,.
• Data Center/Server Farm.
• Design of water distribution systems.
• Distributed computer network topologies.
• Electronic circuit design, known as Evolvable hardware.
• Gene expression profiling analysis.
• File allocation for a distributed system.
• Finding hardware bugs.
• Game Theory Equilibrium Resolution.
• Genetic Algorithm for Rule Set Production
• Economics
• Scheduling applications, including job-shop scheduling. The objective being to schedule jobs in a sequence dependent or non-sequence dependent setup environment in order to maximize the volume of production while minimizing penalties such as tardiness.
• Learning Robot behavior using Genetic Algorithms.
• Learning fuzzy rule base using genetic algorithms.
• Linguistic analysis, including Grammar induction and other aspects of Natural language processing (NLP) such as word sense disambiguation.
• Marketing Mix Analysis
• Mobile communications infrastructure optimization.
• Molecular Structure Optimization (Chemistry).
• Multidimensional Systems
• Multiple criteria production scheduling.
• Multiple population topologies and interchange methodologies.
• Mutation testing
• Neural Networks; particularly recurrent neural networks
• Operon prediction.
• Optimisation of data compression systems, for example using wavelets.
• Parallelization of GAs/GPs including use of hierarchical decomposition of problem domains and design spaces nesting of irregular shapes using feature matching and GAs.
• Plant floor layout.
• Pop music record producer.
• Power electronics design.
• Protein folding and protein/ligand docking.
• Quality control
• Representing rational agents in economic models such as the cobweb model.
• Selection of optimal mathematical model to describe biological systems.
• Software engineering^[]
• Solving the machine-component grouping problem required for cellular manufacturing systems.
• Tactical asset allocation and international equity strategies.
• Timetabling problems, such as designing a non-conflicting class timetable for a large university.
• Training artificial neural networks when pre-classified training examples are not readily obtainable (neuroevolution).
• Traveling Salesman Problem.
• Wireless Sensor/Ad-hoc Networks.

الهامش

ببليوجرافيا

وصلات خارجية

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

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

مصادر

• DigitalBiology.NET Vertical search engine for GA/GP resources
• Genetic Algorithms Index The site Genetic Programming Notebook provides a structured resource pointer to web pages in genetic algorithms field

دروس تدريبية

• An online interactive GA demonstrator to practise or learn how a GA works. Learn step by step or watch global convergence in batch, change population size, crossover rate, mutation rate and selection mechanism, and add constraints.
• A Field Guide to Genetic Programming HTML version of book. A freely downloadable version is also available.
• Introduction to Genetic Algorithms with interactive Java applets For experimenting with GAs online
• A Practical Tutorial on Genetic Algorithm Programming a Genetic Algorithm step by step.
• A Genetic Algorithm Tutorial by Darrell Whitley Computer Science Department Colorado State University An excellent tutorial with lots of theory
• Cross discipline example applications for GAs with references.
• "Essentials of Metaheuristics", 2009 (225 p). Free open text by Sean Luke.
• Global Optimization Algorithms - Theory and Application