حلول لمشكلة البائع المتجول التي حصل عليها نظام الحوسبة القائم على الأميبا. أمثلة لجولات البائع في أربع وخمس و 6 و 7 و 8 مدن ، تم الحصول عليها في التجارب ، حيث يتم رسم كل جولة باللون الأحمر على القنوات المقابلة من الرقم الصحيح. تُظهر اللوحات اليسرى الصور الضوئية المرسلة للحالات الأولية (أظهرت مجموعة من الباحثين اليابانيين من جامعة كيو في طوكيو أن الأميبا قادرة على توليد حلول تقريبية لمشكلة رياضية معقدة بشكل مدهش تعرف باسم
مشكلة البائع المتجول .
مهمة البائع هي واحدة من أشهر مهام التحسين التوافقية ، والتي تتمثل في العثور على الطريق الأكثر ربحية الذي يمر عبر هذه المدن مرة واحدة على الأقل ثم العودة إلى المدينة الأصلية.
بيان تحسين المشكلة ينتمي إلى فئة المشكلات NP- الثابت ، مثل معظم الحالات الخاصة به. إن إصدار "مشكلة القرار" (أي ، المشكلة التي يتم طرح السؤال حول ما إذا كان المسار لم يعد يتجاوز القيمة المعطاة k) ينتمي إلى فئة مشكلات NP-Complete.
تزداد صعوبة حساب الحل الصحيح بشكل كبير مع إضافة المزيد من المدن إلى المهمة. على سبيل المثال ، هناك ثلاث حلول لأربعة مدن ، وبالنسبة لست مدن - 360. في المستقبل ، يستمر النمو المتسارع.
على الرغم من التعقيد الحسابي الكبير ، هناك عدد كبير من الخوارزميات الإرشادية والدقيقة التي يمكن أن تحل بعض الحالات تمامًا بعشرات الآلاف من المدن ،
ويمكن تقريب المشكلات حتى مع ملايين المدن
في حدود 0.05٪ . يحتوي الرابط المشار إليه على محاولات لحل على سبيل المثال 1،904،711 مدينة من الأرض من قاعدة الجمعية الجغرافية الوطنية.
قاعدة الجمعية الجغرافية الوطنية التي تضم 19041111 مدينةفي الوقت الحالي ، سجل الحد الأدنى للمسافة لمدن الأرض هو 7 515 772 107 كم ، تم تعيينه في 13 مارس 2018 باستخدام خوارزمية
LKH الكشف عن مجريات الأمور.
يتم استخدام مشكلة البائع الكلاسيكي في علوم الكمبيوتر كمعيار لخوارزميات التحسين.
الأميبا هي كائنات وحيدة الخلية ليست لديها فكرة عن مدى تعقيد التحسين التوافقي. ليس لديهم أي شيء يشبه عن بعد الجهاز العصبي المركزي ، مما يجعلهم أقل ملائمة المرشحين لحل مشاكل هذا التعقيد. ومع ذلك ، فقد وجد الباحثون اليابانيون أنه يمكن استخدام نوع معين من الأميبا لحساب الحلول شبه المثلى لمشكلة البائع المتجول في ثماني مدن.
وفقًا
لمقال علمي ،
شاركت الأميبا التي تُسمى
Physarum polycephalum ، والتي كانت تُستخدم سابقًا
ككمبيوتر بيولوجي في العديد من التجارب الأخرى ، في التجارب. يعتبر هذا المخلوق مفيدًا بشكل خاص في الحوسبة البيولوجية لأنه يمكنه توسيع مناطق مختلفة من جسمه بحثًا عن طريقة أكثر فعالية للحصول على الطعام ، ويكره الضوء.
لتحويل هذه الآلية الطبيعية للتغذية إلى جهاز كمبيوتر ، وضع الباحثون اليابانيون الأميبا على طبق خاص به 64 قناة ، في اتجاهه يمكن للحيوان أن يمد الجسم. تحاول الأميبا باستمرار توسيع الجسم لتغطية أكبر مساحة ممكنة من لوحة المواد الغذائية. ومع ذلك ، يمكن إضاءة كل قناة في اللوحة ، مما يؤدي إلى خروج الأميبة من هذه القناة من الشعور بالكره إلى الضوء.
لمحاكاة مشكلة البائع المتجول ، تم تعيين رمز لكل مدينة من القنوات الـ 64 الموجودة على اللوحة بين A و H ، بالإضافة إلى رقم من 1 إلى 8 ، مما يشير إلى ترتيب المدن (ترتيب المدن يتوافق مع الترتيب الذي زار به البائع).
لبرمجة الأميبا ، استخدم الباحثون شبكة عصبية تضمنت بيانات عن الوضع الحالي للأميبا والمسافة بين المدن لإلقاء الضوء على قنوات محددة. كانت الشبكة العصبية أكثر عرضة لإلقاء الضوء على المدن (القنوات) بمسافات أكبر بينها.
عندما تتفاعل الخوارزمية والأميبا ، تأخذ الأخيرة شكلاً يمثل حلولًا تقريبية لمشكلة البائع المتجول. والأمر الأكثر إثارة للاهتمام هو أن مقدار الوقت الذي يستغرقه الأميبا للحصول على هذه الحلول المثلى يكبر بشكل
خطي ، على الرغم من أن عدد خيارات الحل يزداد
باطراد . في المستقبل القريب ، سيقوم الباحثون بصنع رقائق تحتوي على عشرات الآلاف من القنوات حتى تتمكن الأميبا من حل مشكلة البائع المتجول في مئات المدن.
تم
نشر المقال العلمي في 19 ديسمبر 2018 في مجلة
Royal Society Open Science (doi: 10.1098 / rsos.180396).