الترميز الثنائي

الترميز (Encoding)
يتكون المجتمع من N من الأفراد (Individuals) و يقوم مصمم الخوارزمية باختيار حجم المجتمع ( عادة يتراوح حجم المجتمع بين 25 إلى 500 فرد) . كل فرد في المجتمع يمثل بواسطة خيط ثابت الطول (Constant String) يسمى كروموسوم (Chromosome) , و يتكون كل كروموسوم من عدد من المواقع تسمى جينات (Genes) و تختلف قيم المواقع باختلاف طريقة الترميز المستخدمة و تكون الصيغة العامة للفرد:-

حيث أن L هو طول الكروموسوم .
في بداية ظهور الخوارزميات الجينية كان طول الكروموسوم ثابت بمعنى :
اذا كان طول الكروموسوم = 3 , فان جميع الكروموسومات في كافة المجتمعات ستتكون من ثلاث جينات. لكن و مع تقدم الابحاث ظهرت اتجاهات تعتمد طول متغير للكروموسوم .
بعد تحديد حجم المجتمع و طول الكروموسوم يتم توليد مجموعة من الأرقام العشوائية تمثل القيم الابتدائية لجينات كافة أفراد المجتمع الابتدائي .
ان ملئ جينات الكروموسوم بالقيم المناسبة يطلق عليها عملية الترميز او التشفير . تمثل الخوارزمية الجينية معاملات المشكلة المراد حلها بهيأة كروموسوم و يعتبر اختيار طريقة ترميز جيّدة و مناسبة للمشكلة احد مفاتيح نجاح الخوارزمية الجينية. هناك عدة طرق للترميز و يعتمد اختيار الطريقة المناسبة على طبيعة المسالة المراد حلها ومن هذه الطرق :-
أ- الترميز الثنائي (Binary encoding)
استخدم هذا الترميز هولاند في خوارزميته الجينية القياسية و هو ابسط أنواع الترميز , وفيه كل جينة في الكروموسوم يمكن أن تأخذ القيمة 0 أو 1 و من هنا جاءت تسميته بالترميز الثنائي.

مثال :

يعاني الترميز الثنائي من مشكلة جرف هامنك (Hamming cliff) وهذه المشكلة تحدث عندما يكون هناك عددين متجاورين عند تمثيلهما بالنظام العشري و لكن التمثيل الثنائي لهما يظهر أن مسافة هامنك (Hamming distance) بينهما كبيرة. و تعرّف مسافة هامنك بين متجهين بأنها عدد المراتب التي تحوي قيماً مختلفة , في التمثيل الثنائي فأن مسافة هامنك بين عددين هي عدد الواحدات الناتجة من عمل XOR بينهما , يُوضّح الشكل الاتي أمثلة لحساب مسافة هامنك بين عددين ثنائيين :
Hamming distance a XOR b b a
3 111 100 011
4 11110 11001 00111
4 1111 1000 0111
أمثلة لحساب مسافة هامنك بين عددين ثنائيين
على الرغم من أن العددين 3 و 4 متتاليان (الفرق بينهما = 1 ) في التمثيل العشري إلا انَّ تمثيلهما بالنظام الثنائي يكشف أن مسافة هامنك بينهما هي 3 و ذلك ما توضحه الحالة الأولى في الشكل السابق , و هذا يعني أن مثل هذا الترميز قد يمنع الخوارزمية الجينية من الوصول إلى العمومية (Global Optimum) في حال أنها علقت في جرف هامنك , تحل هذه المشكلة باستخدام شفرات گري (Gray Code) التي تتميز بان مسافة هامنك بين أي عددين متجاورين تساوي 1. يمكن تحويل العدد الثنائي إلى شفرات گري باستخدام المعادلة الآتية :-

s1 if k =1
gk =
sk+1 XOR sk if k >1
حيث k يمثل رتبة البت (الموقع) , sk يمثل قيمة البت الثنائي في الموقع k بينما gk يمثل قيمة البت المقابل في شفرة گري. يُوضّح الشكل الشفرات الثنائية مع شفرات گري المقابلة لها للأعداد من 0 إلى 7 :
7 6 5 4 3 2 1 0
integer
111 110 101 100 011 010 001 000
Binary
100 101 111 110 010 011 001 000 Gray Code
مقارنة بين الشفرات الثنائية و شفرات گري

تمرين : شفر الاعداد الثانئية المرادفة للاعداد (11-20) باستخدام شفرات گري