لحل أصعب مهام التحسين ، أضف ليزرًا فقط

جهاز غريب يعرف باسم Ising Optical Machine قادر على التحكم في الحركة الجوية ومساعدة ألعاب NFL في جدولة الألعاب.

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

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

انتصار علم الخوارزميات وقانون مور هو أنه يمكننا الآن التعامل مع العديد من مهام التحسين المعقدة ، بما في ذلك مجالات مثل النقل والخدمات اللوجستية والجدولة. معظم العالم الحديث لن يكون قادرًا على العمل بشكل طبيعي بدون هذه الخوارزميات: يتم سنويًا نقل 50 ألف سفينة شحن بضائع ، و 25000 تيراواط ساعة من الكهرباء ، وتحمل أجهزة التوجيه 1 زيتيت من حركة المرور عبر نفسها. كل هذا سيعمل بكفاءة أقل بكثير. ومع ذلك ، تعمل المنظمات غالبًا مع حلول دون المستوى الأمثل بسبب ضيق المواعيد ونقص موارد الكمبيوتر المتاحة. علاوة على ذلك ، لا تزال هناك الكثير من الفرص لتحسين الأساليب التي نستخدمها للمساعدة في حل معظم مشكلات التحسين.

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

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


مهمة البائع: يزداد تعقيد المهام مثل العثور على أقصر طريق بين عدة نقاط مع زيادة عدد النقاط. يمكن أن يساعد وضع نماذج لها تحت ستار مشاكل التحسين Ising على حلها بشكل أسرع.

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

لمدة خمس مدن ، يتم حل المشكلة ببساطة. يمكن حسابها ببساطة عن طريق النظر في جميع المسارات 12 . ومع ذلك ، إذا كان البائع العامل الجاد يعتزم زيارة 50 مدينة ، فإن طريقة البحث التي ترى أن جميع المسارات المحتملة ستكون غير محتملة - سيكون هناك أكثر من هذه المسارات أكثر من العشرون الجديد ، أو 10 ⁶⁰ - واحد و 60 صفر.

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

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


Ising Optimization : في مشكلة Ising هذه ، تكون طاقة النظام أقل عندما يتم توجيه يدور من إلكتروناته في اتجاهات معاكسة لدوران الجيران. يمكن أن تساعد الأنظمة التي يمكنها العثور على الحالة ذات الطاقة الأقل في نموذج Ising على تسريع حل مشكلات التحسين المعقدة.

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

لسنوات عديدة ، يحاول الباحثون إنشاء آلات خاصة لحل مشاكل التحسين. في منتصف الثمانينيات ، اقترح ديفيد تانك ، الذي كان يعمل في مختبرات AT&T Bell ، وجون هوبفيلد ، وكلاهما يعمل في AT&T Bell و Caltech ، استخدام الدوائر الإلكترونية التمثيلية التي تمثل الشبكات العصبية لحل مشكلات التحسين مثل مشكلة البائع المتجول. عملهم أدى إلى عقود من البحث في هذا المجال. في عام 1994 ، اكتشف ليونارد إدمان من جامعة جنوب كاليفورنيا أنه من الناحية النظرية ، يمكن استخدام الحمض النووي لحل مشاكل من هذا النوع. أدت فكرته إلى موجة مماثلة من البحث. ومع ذلك ، أدت هذه المحاولات لتطوير طرق جديدة وفعالة بشكل جذري لحل مشاكل التحسين إلى بدائل عملية لأجهزة الكمبيوتر والتقنيات التقليدية ، والتي لا تزال حتى اليوم الأدوات الرئيسية لحل هذه المشاكل.

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

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

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


آلة Ising الضوئية: يمكن لمذبذب حدودي بصري (OPO) مع التغذية المرتدة للقياس أن يحل مشاكل التحسين المعبّر عنها في نموذج Ising - مجموعة من يدور الإلكترون وتأثيرها على بعضها البعض. تمثل مراحل النبضات الضوئية في OPO الدورات ، ويتم تقديم التأثير في صفيف بوابة قابل للبرمجة بواسطة المستخدم ( PPM ). من الضروري إكمال حوالي مائة تمر عبر النظام قبل أن تصبح الدوافع في OPO قوية بما يكفي لإيجاد حل للمشكلة.

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

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

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

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

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

هناك عدة طرق لإنشاء جهاز Ising باستخدام OPO. مجموعات من NTT ، Caltech ، كورنيل ، وكولومبيا ، من بين أمور أخرى ، لديها نهج مختلفة. النموذج الأولي لآلة Ising ، الذي تم عرضه لأول مرة في جامعة ستانفورد في تجربة تحت إشراف Alireza Marandi (الذي يعمل حاليًا في Caltech) ، استخدم التكنولوجيا التي نواصل العمل عليها بشكل إضافي: مضاعفة OPO مع تقسيم الوقت والاتصال البصري.

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

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


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

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

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

تذكر أن حل مشكلة Ising يعني إيجاد الحد الأدنى من حالة الطاقة لمجموعة من الدورات التي تتفاعل فيها الدورات بطريقة مختلفة ، وتضيف هذه التفاعلات طاقة إضافية إلى إجمالي طاقة النظام. في HME ، تشير كل دفعة إلى زيادة ونقصان. لذلك ، لكل نبضة - وفي الإعداد الخاص بنا استخدمنا 100 - يقوم PPMM بإجراء حسابات ، والتي تشمل القياسات المسجلة لجميع النبضات الأخرى ، والتي ، وفقًا لمشكلة Ising ، يجب أن تؤثر على الدوران قيد الدراسة. ثم يقوم المعالج بتطبيق العمليات الحسابية على إعدادات مُعدِّل الكثافة ومعدل الطور الموجود على أحد مسارات النبض الأساسي. يتم تغذية نبض القاعدة المعدل في حلقة كابل الألياف الضوئية ، حيث يتذبذب نبضات OPO.

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

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

في تجاربنا ، صنعنا أولاً نظامًا بأربعة يدور ، ثم بـ 16 يدور. كانت معلمات المهمة قائمة على الأجهزة في عمليات التثبيت في شكل مقاطع متفرعة من كابل بصري بطول معين. في هذه التجارب ، اكتشفنا بنجاح حالات الحد الأدنى من الطاقة ، وهذا أعطانا الدافع لتطوير هذا النهج. في عام 2016 ، أنشأنا جهاز تغذية مرتكز إلى PPVM قادرًا على حل مشكلات Ising مع 100 يدور. المقارنة بين سرعة منشأتنا مع الأنظمة المتخصصة ، بما في ذلك جهاز " الكم الصلب " التابع لناسا ، أعطانا الثقة في أن آلات Ising OPO يمكن أن تكون محسنات فعالة.

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