هندسة خوارزميات التحسين مع HorusLP

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

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

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

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

المشكلات التي تواجه مطوري خوارزمية التحسين

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

في معظم التخصصات ، يمكن للمطور التخفيف من هذه المشكلة عن طريق اختيار إطار عمل أو مكتبة تساعد في البنية. في الواجهة الأمامية للويب ، يختار العديد من المطورين React أو Angular ؛ في عالم تطوير API ، يمكن لمهندسي البرمجيات الاختيار من Django أو ASP.NET MVC أو Play ، من بين أشياء أخرى كثيرة. ومع ذلك ، عندما يتعلق الأمر بمطور خوارزمية التحسين المتواضع ، هناك عدد قليل جدًا من أدوات الهندسة للمساعدة في إدارة التعقيد المعماري. يُترك المطور لإدارة المتغيرات والقيود والأهداف المختلفة بمفرده. علاوة على ذلك ، من الصعب عمومًا استبطان خوارزميات أبحاث العمليات ، مما يؤدي إلى تفاقم المشكلة.

الغرض الرئيسي من HorusLP هو توفير إطار معماري لتطوير خوارزميات التحسين. من خلال توفير الاتساق الهيكلي ، يسهل إطار العمل التنظيم ويسمح للمطورين بالتركيز على أفضل ما يفعلونه: بناء الخوارزميات.

تحديات سير العمل النموذجية للتحسين

هناك عدة مصادر رئيسية للتعقيد عند تطوير خوارزميات OR:

التعقيد من المتغيرات

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

التعقيد من القيود

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

التعقيد من الأهداف

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

التعقيد من التصحيح

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

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

برنامج HorusLP التعليمي: خوارزمية التحسين ونظرة عامة على واجهة برمجة التطبيقات

بدون مزيد من اللغط ، دعنا نتعمق ونرى ما يمكن أن تقدمه لك مكتبة HorusLP!

نظرًا لأن HorusLP يعتمد على Python و PuLP ، فسنريد تثبيتهما باستخدام النقطة. قم بتشغيل ما يلي في سطر الأوامر:

 Pip install horuslp pulp

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

تحتوي مكتبة HorusLP على واجهة برمجة تطبيقات توضيحية بسيطة جدًا وقليل جدًا من النماذج المعيارية. لنبدأ باستيراد الفئات والمتغيرات الضرورية:

 from horuslp.core.Variables import BinaryVariable # we will be using binary variables, so we will import the BinaryVariable class from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent # We will also need to import the constraint class, variable manager class, the main problem class, and the objective class to define the objective. from horuslp.core.constants import MAXIMIZE # since we're maximizing the resulting value, we want to import this constant

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

 class KnapsackVariables(VariableManager): vars = [ BinaryVariable('camera'), # the first argument is the name of the variable BinaryVariable('figurine'), BinaryVariable('cider'), BinaryVariable('horn') ]

الآن بعد أن تم تحديد المتغيرات ، دعنا نحدد القيود. نقوم بإنشاء قيود عن طريق تصنيف فئة القيد الرئيسية وتنفيذ وظيفة "التعريف" الخاصة بها.

 class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

في وظيفة التعريف ، يمكنك طلب المتغيرات المطلوبة بالاسم. سيحدد إطار العمل المتغير في مدير المتغير ويمرره إلى وظيفة التعريف.

بعد تنفيذ القيد ، يمكننا تنفيذ الهدف. نظرًا لأنه هدف بسيط ، سنستخدم ObjectiveComponent :

 class ValueObjective(ObjectiveComponent): def define(self, camera, figurine, cider, horn): return 5 * camera + 7 * figurine + 2 * cider + 10 * horn

وظيفة التعريف لها إعداد مشابه جدًا لوظيفة تعريف فئة القيد. وبدلاً من إرجاع تعبير القيد ، فإننا نعيد تعبير أفيني.

الآن بعد أن تم تحديد المتغيرات والقيود والأهداف ، دعنا نحدد النموذج:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE

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

 prob = KnapsackProblem() prob.solve()

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

 prob.print_results() print(prob.result_variables)

قم بتشغيل البرنامج النصي ، وسترى الإخراج التالي:

 KnapsackProblem: Optimal camera 0.0 figurine 1.0 cider 0.0 horn 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'camera': 0.0, 'figurine': 1.0, 'cider': 0.0, 'horn': 1.0}

يجب أن ترى حالة المشكلة والقيمة النهائية للمتغيرات والقيمة الهدف وقيمة تعبير القيد. نرى أيضًا القيم الناتجة للمتغيرات كقاموس.

وها هو لدينا ، أول مشكلة HorusLP في حوالي 35 سطرًا!

في الأمثلة القادمة ، سوف نستكشف بعض الميزات الأكثر تعقيدًا لمكتبة HorusLP.

باستخدام VariableGroups

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

قم بتغيير عبارات الاستيراد كما يلي:

 from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent from horuslp.core.constants import MAXIMIZE

نحتاج الآن أيضًا إلى تغيير الإعلانات المتغيرة على الحقيبة كما يلي:

 class KnapsackVariables(VariableManager): vars = [ BinaryVariableGroup('objects', [ 'camera', 'figurine', 'cider', 'horn' ]) ]

المتغير الأول هو اسم مجموعة المتغيرات ، والمتغير الثاني هو قائمة بأسماء المتغيرات داخل تلك المجموعة.

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

 class SizeConstraint(Constraint): def define(self, objects): return 2 * objects['camera'] + 4 * objects['figurine'] + 7 * objects['cider'] + 10 * objects['horn'] <= 15 class ValueObjective(ObjectiveComponent): def define(self, objects): return 5 * objects['camera'] + 7 * objects['figurine'] + 2 * objects['cider'] + 10 * objects['horn']

الآن يمكننا استخدام نفس تعريف المشكلة وتشغيل الأوامر:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [SizeConstraint] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results() print(prob.result_variables)

يجب أن ترى هذا في الإخراج الخاص بك:

 KnapsackProblem: Optimal objects[camera] 0.0 objects[figurine] 1.0 objects[cider] 0.0 objects[horn] 1.0 ValueObjective: 17.00 SizeConstraint: 14.00 {'objects': {'camera': 0.0, 'figuring': 1.0, 'cider': 0.0, 'horn': 1.0}}

إدارة القيود المتعددة

النماذج ذات القيد الفردي نادرة نسبيًا. عند العمل مع قيود متعددة ، من الجيد وجود جميع القيود في مكان واحد حتى يمكن تتبعها وإدارتها بسهولة. HorusLP يجعل ذلك طبيعيًا.

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

ارجع إلى النموذج الذي طبقناه في البرنامج التعليمي الأول. أضف القيد التالي:

 class MustHaveItemConstraint(Constraint): def define(self, camera): return camera >= 1

لإضافة القيد إلى النموذج ، نحتاج ببساطة إلى إضافته إلى تعريف المشكلة كما يلي:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, MustHaveItemConstraint # just add this line :) ] sense = MAXIMIZE

قم بتشغيل المشكلة ، وسترى الإخراج التالي:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

يجب أن ترى القيد الجديد الذي تتم طباعته في stdout ، وقيم المتغير المثلى التي تم تغييرها.

إدارة القيود التابعة والمجموعات المقيدة

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

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

للتعبير عن هذه المجموعات ، يمكننا استخدام ميزة القيود التابعة لتعريفات القيد الخاصة بنا. لمعرفة كيف يمكن استخدام ميزة القيد التابعة ، قم بإعادة SizeConstraint للمشكلة السابقة على النحو التالي:

 class SizeConstraint(Constraint): dependent_constraints = [MustHaveItemConstraint] def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15

والآن لاختبار أن القيود التابعة يتم تنفيذها تلقائيًا ، MustHaveItemConstraint من تعريف المشكلة:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [ SizeConstraint, ] sense = MAXIMIZE

وقم بتشغيل الكود مرة أخرى ، وسترى ما يلي في stdout:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 cider 0.0 horn 1.0 ValueObjective: 15.00 SizeConstraint: 12.00 MustHaveItemConstraint: 1.00

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

إدارة أهداف مرجحة متعددة

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

لنفترض أننا أردنا تحيز الخوارزمية لاختيار التمثال وعصير التفاح. دعنا نعيد تشكيل الكود من القسم السابق لاستخدام CombinedObjective .

أولاً ، قم باستيراد فئة CombinedObjective مثل:

 from horuslp.core import CombinedObjective

يمكننا تنفيذ عنصر موضوعي مستقل مثل:

 class ILoveCiderFigurineObjectiveComponent(ObjectiveComponent): def define(self, figurine, cider): return figurine + cider

الآن يمكننا الجمع بين هدف القيمة وهدف عصير التفاح / الشكل من خلال تنفيذ CombinedObjective :

 class Combined(CombinedObjective): objectives = [ (ILoveCiderFigurineObjectiveComponent, 2), # first argument is the objective, second argument is the weight (ValueObjectiveComponent, 1) ]

الآن دعنا نغير تعريف المشكلة على النحو التالي:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = Combined constraints = [SizeConstraint] sense = MAXIMIZE

قم بتشغيل المشكلة ، وسترى الإخراج التالي:

 KnapsackProblem: Optimal camera 1.0 figurine 1.0 cider 1.0 horn 0.0 Combined: 18.00 ILoveCiderFigurineObjectiveComponent: 2.00 * 2 ValueObjectiveComponent: 14.00 * 1 SizeConstraint: 13.00 MustHaveItemConstraint: 1.00

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

البحث عن قيود غير متوافقة

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

لنفترض أننا أضفنا قيودًا وانتهى بنا الأمر بمجموعة القيود التالية:

 class SizeConstraint(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 15 class SizeConstraint2(Constraint): def define(self, camera, figurine, cider, horn): return 2 * camera + 4 * figurine + 7 * cider + 10 * horn <= 20 class MustHaveItemConstraint(Constraint): def define(self, cider): return cider >= 1 class IncompatibleConstraint1(Constraint): def define(self, camera): return camera >= 1 class IncompatibleConstraint2(Constraint): def define(self, camera): return camera <= 0

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

افترض أيضًا أن القيود مجمعة بالطريقة التالية ، مما قد يجعل عملية الكشف أكثر صعوبة:

 class CombinedConstraints1(Constraint): dependent_constraints = [SizeConstraint2, IncompatibleConstraint1] class CombinedConstraints2(Constraint): dependent_constraints = [SizeConstraint, IncompatibleConstraint2] # MustHaveItemConstraint will be included in the problem definition independently

هنا تعريف المشكلة:

 class KnapsackProblem(Problem): variables = KnapsackVariables objective = ValueObjective constraints = [CombinedConstraints1, CombinedConstraints2, MustHaveItemConstraint] sense = MAXIMIZE

قم بتشغيل المشكلة ، وسترى النتيجة التالية:

 KnapsackProblem: Infeasible

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

 prob.print_results(find_infeasible=True)

سهل هكذا! قم بتشغيل الكود ، والآن يجب أن ترى ما يلي كإخراج:

 KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('CombinedConstraints1', 'CombinedConstraints2')

رائعة! لقد أثبتنا الآن أن MustHaveItemConstraint ليس سبب عدم الجدوى وأن المشكلة ترجع إلى CombinedConstraints1 و CombinedConstraints2 .

هذا يعطينا بعض المعلومات ، ولكن بين القيود مجتمعة هناك أربعة قيود تابعة. هل يمكننا تحديد أي من القيود الأربعة غير متوافق؟ نعم. قم بتعديل استدعاء print_results الخاص بك على هذا النحو:

 prob.print_results(find_infeasible=True, deep_infeasibility_search=True)

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

 KnapsackProblem: Infeasible Finding incompatible constraints... Incompatible Constraints: ('IncompatibleConstraint1', 'IncompatibleConstraint2')

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

بناء الخوارزميات من ملفات البيانات

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

 { "items": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "figurine", "value": 7, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "horn", "value": 10, "weight": 10}, {"name": "banana", "value": 9, "weight": 2} ], "capacity": 15 }

يمكننا القيام بذلك من خلال الاعتماد على دعم kwargs لوظيفة "التعريف" التي ننفذها للقيود والأهداف.

دعنا نعدل الكود من مشكلة الحقيبة البسيطة (المشكلة التي قمنا بتنفيذها في القسم 1 من البرنامج التعليمي). أولاً ، لنضع سلسلة JSON في الملف. بالطبع ، نقرأه عادةً من مصدر خارجي ، ولكن من أجل البساطة ، دعونا نحتفظ بكل شيء في ملف واحد. أضف ما يلي إلى التعليمات البرمجية الخاصة بك:

 JSON = ''' { "items": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "figurine", "value": 7, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "horn", "value": 10, "weight": 10}, {"name": "banana", "value": 9, "weight": 2} ], "capacity": 15 } '''

دعنا نتأكد أيضًا من أن برنامجنا سيكون قادرًا على تحليله. أضف ما يلي إلى بيانات الاستيراد الخاصة بك:

 Import json

الآن ، دعنا نعدل رمز الإعداد المتغير لدينا على النحو التالي:

 mip_cfg = json.loads(JSON) class KnapsackVariables(VariableManager): vars = [ BinaryVariable(i['name']) for i in mip_cfg['items'] ]

سيحدد هذا متغيرًا لكل عنصر من العناصر في JSON ، ويطلق عليه اسمًا مناسبًا.

دعونا نغير القيد والتعريفات الموضوعية مثل ذلك:

 class CapacityConstraint(Constraint): def define(self, **kwargs): item_dict = {i['name']: i['weight'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs) <= mip_cfg['capacity'] class ValueObjective(ObjectiveComponent): def define(self, **kwargs): item_dict = {i['name']: i['value'] for i in mip_cfg['items']} return sum(kwargs[name] * item_dict[name] for name in kwargs)

من خلال طلب **kwargs بدلاً من المتغيرات المحددة ، تحصل وظيفة define على قاموس يحتوي على جميع المتغيرات بالاسم. يمكن لوظيفة تعريف القيد الوصول إلى المتغيرات من القاموس.

ملاحظة: بالنسبة للمجموعات المتغيرة ، سيكون قاموسًا متداخلًا حيث يكون المستوى الأول هو اسم المجموعة والمستوى الثاني هو اسم المتغير.

الباقي واضح ومباشر:

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

قم بتشغيل هذا البرنامج وسترى الإخراج التالي:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00

تحديد المقاييس المخصصة في HorusLP

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

لنفترض أننا أردنا تتبع عدد الفاكهة التي كان النموذج من القسم السابق يضعها في الحقيبة. لتتبع هذا يمكننا تحديد مقياس مخصص. لنبدأ باستيراد فئة المقاييس الأساسية:

 From horuslp.core import Metric

الآن دعنا نحدد المقياس المخصص:

 class NumFruits(Metric): name = "Number of Fruits" def define(self, apple, banana): return apple + banana

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

نحتاج الآن إلى إضافة المقياس إلى تعريف المشكلة. الواجهة هنا مرة أخرى مشابهة جدًا لتعريف القيد:

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [CapacityConstraint] objective = ValueObjective metrics = [NumFruits] sense = MAXIMIZE

قم بتشغيل هذا وسترى الإخراج التالي:

 KnapsackProblem: Optimal camera 1.0 figurine 0.0 apple 0.0 horn 1.0 banana 1.0 ValueObjective: 24.00 CapacityConstraint: 14.00 Number of Fruits: 1.00

يمكنك رؤية عدد الثمار المطبوعة في الأسفل.

التعامل مع مشكلة أكثر تعقيدًا: حقيبتان

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

 { "fragile": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "glasses", "value": 3, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "pear", "value": 5, "weight": 3}, {"name": "banana", "value": 9, "weight": 2} ], "durable": [ {"name": "figurine", "value": 7, "weight": 4}, {"name": "horn", "value": 10, "weight": 10}, {"name": "leatherman", "value": 10, "weight": 3} ], "suitcase_capacity": 15, "bag_capacity": 20 }

دعونا نرى كيف يغير هذا النموذج. لنبدأ بسجل فارغ لأن النموذج سيكون مختلفًا تمامًا. ابدأ بإعداد المشكلة:

 import json from horuslp.core.Variables import BinaryVariableGroup from horuslp.core import Constraint, VariableManager, Problem, Metric, ObjectiveComponent from horuslp.core.constants import MAXIMIZE JSON = ''' { "fragile": [ {"name": "camera", "value": 5, "weight": 2}, {"name": "glasses", "value": 3, "weight": 4}, {"name": "apple", "value": 2, "weight": 7}, {"name": "pear", "value": 5, "weight": 3}, {"name": "banana", "value": 9, "weight": 2} ], "durable": [ {"name": "figurine", "value": 7, "weight": 4}, {"name": "horn", "value": 10, "weight": 10}, {"name": "leatherman", "value": 10, "weight": 3} ], "suitcase_capacity": 15, "bag_capacity": 20 } ''' mip_cfg = json.loads(JSON)

لنقم الآن بإعداد المتغيرات. سنقوم بإعداد متغير ثنائي لكل مجموعة عناصر / حاوية محتملة.

 class KnapsackVariables(VariableManager): vars = [ # suitcase can hold both fragile and durable goods BinaryVariableGroup('suitcase_f', [i['name'] for i in mip_cfg['fragile']]), BinaryVariableGroup('suitcase_d', [i['name'] for i in mip_cfg['durable']]), # bag can only hold durable goods. BinaryVariableGroup('bag_d', [i['name'] for i in mip_cfg['durable']]) ]

نريد الآن تطبيق قيود الوزن لكل من الحقيبة والحقيبة.

 class SuitcaseCapacityConstraint(Constraint): def define(self, suitcase_d, suitcase_f): fragile_weight = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_weight = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_weight + durable_weight <= mip_cfg['suitcase_capacity'] class BagCapacityConstraint(Constraint): def define(self, bag_d): durable_weight = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return durable_weight <= mip_cfg['bag_capacity']

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

لإضافة هذا القيد ، نحتاج إلى تكرار جميع العناصر المتينة ، والعثور على متغير "in the suitcase" ومتغير "in the bag" والتأكيد على أن مجموع هذه المتغيرات أقل من 1.

يمكننا تحديد القيود التابعة ديناميكيًا بسهولة تامة في HorusLP:

 class UniquenessConstraints(Constraint): def __init__(self): super(UniquenessConstraints, self).__init__() # call the dependent constraint builder function for every durable item, and push them into dependent constraints. dependent_constraints = [self.define_uniqueness_constraint(item) for item in mip_cfg['durable']] self.dependent_constraints = dependent_constraints def define_uniqueness_constraint(self, item): # classes are first-class objects in python, so we can define a class within this function and return it class UQConstraint(Constraint): # we name the constraint based on the item this is for, so that debugging is easier. name = "Uniqueness_%s" % item['name'] def define(self, suitcase_d, bag_d): # the define function can access the variables much in the same way as other functions return suitcase_d[item['name']] + bag_d[item['name']] <= 1 return UQConstraint

الآن بعد أن تم تحديد القيود ، فلنقم ببناء الهدف. الهدف هو ببساطة مجموع كل القيم التي نحصل عليها من جميع العناصر الموجودة في الحاويات. هكذا:

 class TotalValueObjective(ObjectiveComponent): def define(self, suitcase_f, suitcase_d, bag_d): fragile_value = sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) durable_value_s = sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) durable_value_d = sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) return fragile_value + durable_value_s + durable_value_d

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

 class SuitcaseFragileWeightMetric(Metric): def define(self, suitcase_f): return sum([suitcase_f[i['name']] * i['weight'] for i in mip_cfg['fragile']]) class SuitcaseDurableWeightMetric(Metric): def define(self, suitcase_d): return sum([suitcase_d[i['name']] * i['weight'] for i in mip_cfg['durable']]) class BagWeightMetric(Metric): def define(self, bag_d): return sum([bag_d[i['name']] * i['weight'] for i in mip_cfg['durable']])

الآن انتهينا من جميع الأجزاء ، فلنقم بإنشاء مثيل للمشكلة وتشغيل النموذج:

 class KnapsackProblem(Problem): variables = KnapsackVariables constraints = [SuitcaseCapacityConstraint, BagCapacityConstraint, UniquenessConstraints] objective = TotalValueObjective metrics = [SuitcaseDurableValueMetric, SuitcaseFragileValueMetric, BagValueMetric] sense = MAXIMIZE prob = KnapsackProblem() prob.solve() prob.print_results()

قم بتشغيل هذا ، وسترى الإخراج التالي في stdout الخاص بك:

 KnapsackProblem: Optimal suitcase_f[camera] 1.0 suitcase_f[glasses] 1.0 suitcase_f[apple] 1.0 suitcase_f[pear] 0.0 suitcase_f[banana] 1.0 suitcase_d[figurine] 0.0 suitcase_d[horn] 0.0 suitcase_d[leatherman] 0.0 bag_d[figurine] 1.0 bag_d[horn] 1.0 bag_d[leatherman] 1.0 TotalValueObjective: 32.00 SuitcaseCapacityConstraint: 15.00 BagCapacityConstraint: 17.00 Uniqueness_figurine: 1.00 Uniqueness_horn: 1.00 Uniqueness_leatherman: 1.00 SuitcaseDurableWeightMetric: 0.00 SuitcaseFragileWeightMetric: 15.00 BagWeightMetric: 17.00

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

سيناريو أكبر وأكثر واقعية: مشكلة التوظيف

تهانينا ، إذا كنت قد وصلت إلى هذا الحد في برنامجنا التعليمي HorusLP! لديك الآن فكرة جيدة عن كيفية استخدام HorusLP.

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

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

لذلك لنبدأ بإعداد المشكلة:

 from horuslp.core.Variables import BinaryVariableGroup, IntegerVariableGroup from horuslp.core import Constraint, VariableManager, Problem, ObjectiveComponent, CombinedObjective from horuslp.core.constants import MINIMIZE shift_requirements = [1, 4, 3, 5, 2] # the number of workers we need to staff for each shift # the availability and pay rates of each of the employees workers = { "Melisandre": { "availability": [0, 1, 4], "cost": 20 }, "Bran": { "availability": [1, 2, 3, 4], "cost": 15 }, "Cersei": { "availability": [2, 3], "cost": 35 }, "Daenerys": { "availability": [3, 4], "cost": 35 }, "Theon": { "availability": [1, 3, 4], "cost": 10 }, "Jon": { "availability": [0, 2, 4], "cost": 25 }, "Tyrion": { "availability": [1, 3, 4], "cost": 30 }, "Jaime": { "availability": [1, 2, 4], "cost": 20 }, "Arya": { "availability": [0, 1, 3], "cost": 20 } } # the following people can't work together, sadly. ban_list = { ("Daenerys", "Jaime"), ("Daenerys", "Cersei"), ("Jon", "Jaime"), ("Jon", "Cersei"), ("Arya", "Jaime"), ("Arya", "Cersei"), ("Arya", "Melisandre"), ("Jaime", "Cersei") } # Dothraki Staffing Corp will provide us with expensive temp workers DOTHRAKI_MAX = 10 DOTHRAKI_COST = 45

الآن دعنا نحدد المتغيرات ، والتي ستكون في هذه الحالة متغيرات ثنائية تحدد ما إذا كان يجب على العامل العمل في نوبته ، ومتغيرات الأعداد الصحيحة التي تحدد عدد dothrakis الذي نوظفه لكل وردية:

 class StaffingVariables(VariableManager): vars = [] def __init__(self): # like dependent constraints, we can dynamically define variables in the init function super(StaffingVariables, self).__init__() # regular workers varkeys = [] for employee, availability_info in workers.items(): for shift in availability_info['availability']: varkeys.append((employee, shift)) self.vars.append(BinaryVariableGroup('employee_shifts', varkeys)) # dothrakis dothraki_keys = [i for i in range(len(shift_requirements))] self.vars.append(IntegerVariableGroup('dothraki_workers', dothraki_keys, 0, DOTHRAKI_COST))

لننفذ الآن القيد الذي يتطلب منا توفير موظفين كافيين لكل وردية:

 class SufficientStaffingConstraint(Constraint): # we need to staff people sufficiently dependent_constraints = [] def __init__(self): super(SufficientStaffingConstraint, self).__init__() for shift_num, shift_req in enumerate(shift_requirements): self.dependent_constraints.append(self.build_shift_constraint(shift_num, shift_req)) def build_shift_constraint(self, sn, sr): class ShiftConstraint(Constraint): name = "shift_requirement_%d" % sn def define(self, employee_shifts, dothraki_workers): variables = [val for key, val in employee_shifts.items() if key[1] == sn] variables.append(dothraki_workers[sn]) return sum(variables) >= sr return ShiftConstraint

الآن ، نحن بحاجة إلى تنفيذ القيود التي تمنع أشخاصًا معينين من العمل مع بعضهم البعض:

 class PersonalConflictsConstraint(Constraint): # some people can't work together dependent_constraints = [] def __init__(self): super(PersonalConflictsConstraint, self).__init__() for person_1, person_2 in ban_list: for shift in range(len(shift_requirements)): self.dependent_constraints.append(self.build_conflict_constraint(person_1, person_2, shift)) def build_conflict_constraint(self, p1, p2, s): class ConflictConstraint(Constraint): name = "Conflict_%s_%s_%d" % (p1, p2, s) def define(self, employee_shifts): if (p1, s) in employee_shifts and (p2, s) in employee_shifts: return employee_shifts[p1, s] + employee_shifts[p2, s] <= 1 return True # returning true will make the constraint do nothing return ConflictConstraint

And finally the labor standards constraint. We'll implement this one slightly differently for demonstrative purposes:

 class LaborStandardsConstraint(Constraint): # we can make someone work more than two shifts a day. dependent_constraints = [] def __init__(self): super(LaborStandardsConstraint, self).__init__() for worker in workers.keys(): # we don't need a constraint builder function, but in those circumstances # we need to set the needed values as class variables and refer to them # via the self keyword due to how python's closure system works class LaborConstraint(Constraint): # we can't use worker directly! wk = worker name = "labor_standard_%s" % worker def define(self, employee_shifts): # we need to access the worker using self. Change self.wk to worker to see # why we need to do this worker_vars = [var for key, var in employee_shifts.items() if key[0] == self.wk] return sum(worker_vars) <= 2 self.dependent_constraints.append(LaborConstraint)

And now let's set up the objectives. The dothraki cost and regular employee costs are calculated very differently, so we'll put them in separate objective components:

 class CostObjective(ObjectiveComponent): # this is the cost function for all the named workers def define(self, employee_shifts, dothraki_workers): costs = [ workers[key[0]]['cost'] * var for key, var in employee_shifts.items() ] return sum(costs) class DothrakiCostObjective(ObjectiveComponent): # don't forget the Dothrakis def define(self, dothraki_workers): dothraki_costs = [ dothraki_workers[sn] * DOTHRAKI_COST for sn in dothraki_workers ] return sum(dothraki_costs) class TotalCostObjective(CombinedObjective): objectives = [ (CostObjective, 1), (DothrakiCostObjective, 1) ]

And now we can define and run the problem:

 class StaffingProblem(Problem): variables = StaffingVariables objective = TotalCostObjective constraints = [SufficientStaffingConstraint, PersonalConflictsConstraint, LaborStandardsConstraint] sense = MINIMIZE # we're minimizing this time, not maximizing. if __name__ == '__main__': prob = StaffingProblem() prob.solve() prob.print_results()

Run the script and you should see the following:

 StaffingProblem: Optimal employee_shifts[('Melisandre', 0)] 0.0 employee_shifts[('Melisandre', 1)] 1.0 employee_shifts[('Melisandre', 4)] 1.0 employee_shifts[('Bran', 1)] 0.0 employee_shifts[('Bran', 2)] 1.0 employee_shifts[('Bran', 3)] 1.0 employee_shifts[('Bran', 4)] 0.0 employee_shifts[('Cersei', 2)] 0.0 employee_shifts[('Cersei', 3)] 0.0 employee_shifts[('Daenerys', 3)] 1.0 employee_shifts[('Daenerys', 4)] 0.0 employee_shifts[('Theon', 1)] 1.0 employee_shifts[('Theon', 3)] 1.0 employee_shifts[('Theon', 4)] 0.0 employee_shifts[('Jon', 0)] 0.0 employee_shifts[('Jon', 2)] 1.0 employee_shifts[('Jon', 4)] 0.0 employee_shifts[('Tyrion', 1)] 1.0 employee_shifts[('Tyrion', 3)] 1.0 employee_shifts[('Tyrion', 4)] 0.0 employee_shifts[('Jaime', 1)] 1.0 employee_shifts[('Jaime', 2)] 0.0 employee_shifts[('Jaime', 4)] 1.0 employee_shifts[('Arya', 0)] 1.0 employee_shifts[('Arya', 1)] 0.0 employee_shifts[('Arya', 3)] 1.0 dothraki_workers[0] 0.0 dothraki_workers[1] 0.0 dothraki_workers[2] 1.0 dothraki_workers[3] 0.0 dothraki_workers[4] 0.0 TotalCostObjective: 335.00 CostObjective: 290.00 * 1 DothrakiCostObjective: 45.00 * 1 shift_requirement_0: 1.00 shift_requirement_1: 4.00 shift_requirement_2: 3.00 shift_requirement_3: 5.00 shift_requirement_4: 2.00 Conflict_Jon_Cersei_2: 1.00 Conflict_Jon_Jaime_2: 1.00 Conflict_Jon_Jaime_4: 1.00 Conflict_Daenerys_Cersei_3: 1.00 Conflict_Daenerys_Jaime_4: 1.00 Conflict_Arya_Jaime_1: 1.00 Conflict_Arya_Cersei_3: 1.00 Conflict_Arya_Melisandre_0: 1.00 Conflict_Arya_Melisandre_1: 1.00 Conflict_Jaime_Cersei_2: 0.00 labor_standard_Melisandre: 2.00 labor_standard_Bran: 2.00 labor_standard_Cersei: 0.00 labor_standard_Daenerys: 1.00 labor_standard_Theon: 2.00 labor_standard_Jon: 1.00 labor_standard_Tyrion: 2.00 labor_standard_Jaime: 2.00 labor_standard_Arya: 2.00

If you compare this with the problem we implemented in the previous tutorial, you should see that the results match.

تغليف

Congratulations for making it through our first HorusLP tutorial! You're now a competent practitioner of HorusLP.

I hope that this article convinced you of the benefits of architecting your MIP models, and that you will make use of HorusLP in your coming projects. You can find the HorusLP source code, as well as the code for all the tutorials, on GitHub. Additional HorusLP documentation and a tutorial page will be added to GitHub very soon.

As HorusLP is a fairly new project, we would love to hear from you and incorporate your input. If you have any questions, comments, or suggestions, please drop me a line either through Toptal or using the contact information you can find on GitHub. I hope to hear from you soon!