تنزيل adaptive large neighbourhood search - تنزيل رمز مصدر adaptive large neighbourhood search

adaptive large neighbourhood search

شفرة المصدر الأخرى

v0.2

تنزيل

بحث حي كبير التكيف

هذا هو تنفيذ C ++ رأس فقط لخوارزمية البحث عن الجيران الكبير (الموازي) ، التي ابتكرها Ropke و Pisinger. يعتمد الرمز بشكل فضفاض على التنفيذ الأصلي الذي تفضله ستيفان روبك معي.

تم تطوير إطار ALNS الأصلي في هذه الورقة:

 @article { ropke_2006 ,
    title = { An adaptive large neighborhood search heuristic for the pickup and delivery problem with time windows } ,
    author = { Ropke, Stefan and Pisinger, David } ,
    year = 2006 ,
    journal = { Transportation Science } ,
    volume = 40 ,
    number = 4 ,
    pages = { 455--472 } ,
    doi = { 10.1287/trsc.1050.0135 }
}

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

 @article { ALNS_Acceptance_Criteria ,
  title = { A comparison of acceptance criteria for the {Adaptive Large Neighbourhood Search} metaheuristic } ,
  author = { Santini, Alberto and Ropke, Stefan and Hvattum, Lars Magnus } ,
  journal = { {Journal of Heuristics} } ,
  volume = 24 ,
  issue = 5 ,
  pages = { 783--815 } ,
  year = 2018 ,
  doi = { 10.1007/s10732-018-9377-x }
}

الاستخدام

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

مثيل المشكلة وحل المشكلة

يجب على المستخدم تنفيذ:

كائن يقوم بتنفيذ مثيل للمشكلة ، مع طريقة عامة getInstanceSize() التي تُرجع حجم المثيل (على سبيل المثال ، عدد القمم في مثيل TSP).
فئة تمثل حل المشكلة ، مع طريقة عامة getCost() إعادة تكلفة لتقليل (على سبيل المثال ، طول جولة TSP).
فئة فرعية من InitialSolutionCreator لإنتاج حل أولي للمشكلة.

بمجرد أن يكون هذا في مكانه ، يمكن للمستخدم إنشاء مثيل لكائن PALNS . على سبيل المثال:

 auto alns = PALNS<TSPInstance, TSPSolution>{instance};

عندما يكون TSPInstance هو نمذجة الفئة مثيل المشكلة ، و TSPSolution هو نمذجة حل المشكلة. يجب على المستخدم توفير الوظائف المذكورة أعلاه على الأقل. على سبيل المثال:

std:: uint32_t TSPInstance::getInstanceSize () const {
    return this -> numberOfVertices ;
}

double TSPSolution::getCost () const {
    return this -> tourLength ;
}

علاوة على ذلك ، نظرًا لأن طريقة ALNS تبدأ من حل ملموسة ، يجب على المستخدم توفير منشئ حلول أولي:

 struct TSPRandomSolutionCreator : InitialSolutionCreator<TSPSolution, TSPInstance> {
    TSPSolution create_initial_solution ( const TPSInstance& instance, std::mt19937& mt) {
        return TSPSolution::shuffled_vertices (mt);
    }
}

للاستنساخ ، يمكن لمبدع الحلول الأولي استخدام مولد أرقام العشوائي الزائفة التي تم تمريرها بواسطة إطار ALNS ، من النوع std::mt19937 (من رأس <random> ).

تدمير وإصلاح طرق

سوف تستمد أساليب التدمير والإصلاح ، على التوالي ، من فئات القاعدة DestroyMethod RepairMethod . يجب أن ينفذ الفصل المورث من DestroyMethod طريقتين:

void destroy_solution(Solution sol&, std::mt19937& mt) ، الذي يأخذ حلًا بالرجوع إليه (و prng ، إذا كنت في حاجة إليه) ويدمرها في مكانها.
std::unique_ptr<DestroyMethod<Solution>> clone() const ، والذي يعيد فريدًا unique_ptr إلى الفئة الأساسية DestroyMethod تستنسخ طريقة التدمير.

وبالمثل ، يجب أن تنفذ فئة وراثة من RepairMethod :

void repair_solution(Solution& sol, std::mt19937& mt) ، الذي يأخذ حل (تم تدميره) بالرجوع إليه (و prng ، إذا كنت في حاجة إليه) وإصلاحه في مكانه.
std::unique_ptr<RepairMethod<Solution>> clone() const ، الذي يعيد a unique_ptr إلى استنساخ الفئة الأساسية RepairMethod طريقة الإصلاح.

على سبيل المثال:

 struct RandomDestroy : public DestroyMethod <TSPSolution> {
    void destroy_solution (TSPSolution& solution, std::mt19937& mt) {
        std::bernoulli_distribution d ( 0.1 );

        for ( const auto & v : solution. visited_vertices ()) {
            if ( d (mt)) {
                solution. queue_vertex_removal (v);
            }
        }

        solution. remove_queued_vertices ();
    }

    std::unique_ptr<DestroyMethod<TSPSolution>> clone () const {
        return std::make_unique<DestroyMethod<TSPSolution>>();
    }
};

struct GreedyRepair : public RepairMethod <TSPSoution> {
    void repair_solution (Solution& sol, std::mt19937& mt) {
        for ( const auto & v : solution. missing_vertices ()) {
            solution. insert_vertex_in_best_position (v);
        }
    }

    std::unique_ptr<RepairMethod<TSPSolution>> clone () const {
        return std::make_unique<RepairMethod<TSPSolution>>();
    }
};

مكونات أخرى

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

on_algorithm_start الذي يسمى قبل التكرار الأول ALNS.
on_prerun_end الذي يتم استدعاؤه عند الانتهاء من المركز قبل (انظر معلمات القسم أدناه).
on_iteration_end الذي يسمى في نهاية كل تكرار.
on_many_iters_without_improvement التي تسمى بعد عدد محدد من قبل المستخدم من التكرارات المتتالية دون تحسين الحل الأفضل (انظر معلمات القسم أدناه).

حدود

يتم تعيين جميع المعلمات من الإطار metaheuristic على تحرير ملف Params.json . تم وصفها أدناه:

prerun-iterations : عدد التكرارات الأولية التي يمكن أن تستخدمها الخوارزمية لمحاولة ضبط معلمات القبول تلقائيًا. هذا ليس إلزاميًا ويمكن ضبطه على الصفر.
total-iterations : حد صعب على عدد التكرارات.
timeout-s : حدود صلبة في وقت وحدة المعالجة المركزية للخوارزمية.
iters-without-improvement-max : حدود صلبة على عدد التكرارات المتتالية دون تحسين الحل الأفضل. إنه ينهي الجري مبكرًا عندما يكون عالقًا في وضع المناظر الطبيعية المسطحة .
iters-without-improvement-alarm : إذا تم تعيينه ، وإذا قدم المستخدم زائرًا خوارزمية ، فبإطار هذا التكرارات المتتالية ، سنقوم باستدعاء on_many_iters_without_improvement . يمكن للمستخدم استخدام هذه الآلية لمحاولة الهروب من Optima المحلي. على سبيل المثال ، يمكن أن تطبق طريقة تدمير أقوى ، أو تنويع الاستدلال.
iterations-without-syncing-threads : في الإصدار الموازي من الخوارزمية ، هذا هو عدد التكرارات التي لا تتم مزامنة المعلومات التي تتصرف فيها وتتصرف مثل نسخ مستقلة من خوارزمية Alns. عند مزامنة الخيط ، تتم مشاركة الأوزان القبول/تدمير الحل والحل الحالي.
prob-return-to-best-known : في كل تكرار ، سيحل الحل المعروف محل الحل الحالي بهذا الاحتمال. يعد Zero افتراضيًا جيدًا ، ولكن يمكن للمستخدم تعيين قيمة أعلى لصالح التكثيف على التنويع.
acceptance-criterion : أحد معايير القبول المحددة مسبقًا. يتم سرد القيم المحتملة في acceptance-criterion-possible-values المفتاح (غير المستخدمة).
acceptance-params-base : تختلف بعض معلمات القبول أثناء تشغيل الخوارزمية. تحدد هذه المعلمة ، التي يمكن أن تأخذ time القيم iterations ما إذا كان ينبغي اعتبار الحد الزمني ( timeout-s ) أو حد التكرار ( total-iterations ) لتقدير متى ستنتهي التشغيل.
scores : هذه هي المضاعفات المستخدمة لتحديث درجات التدمير/الإصلاح في كل تكرار. يجب على المستخدمين توفير أربعة مضاعفات:
- global-best إذا كان الحل الجديد أفضل من الحل الأفضل السابق ، وإلا
- improved إذا كان الحل الجديد أفضل من الحل الحالي ، وإلا
- accepted إذا تم قبول الحل الجديد من خلال معيار القبول.
- يحدد المضاعف الرابع ، decay ، مدى سرعة تأثير القيم الثلاث المذكورة أعلاه على درجات الأساليب. الافتراضي عاقل أقل بقليل من 1.0 ، لضمان أن الدرجات تتغير بسلاسة.
parameter-tuning-file : إذا كان إجراء ضبط المعلمة ، فهذا هو اسم الملف حيث سيتم حفظ النتائج.
results-log-basename : الاسم الأساسي لملفات النتائج.

معلمات القبول

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

قبول الصلب محاكاة
- init-ratio-50p : الحلول أسوأ بكثير من القائمة الحالية مع احتمال 50 ٪ في بداية المدى.
- end-ratio-50p : الحلول أسوأ بكثير من القائمة الحالية مع احتمال 50 ٪ في نهاية المدى.
- end-ratio-50p-refers-to-initial : إذا تم ضبطها على true ، في وصف end-ratio-50p استبدال "One Current" بـ "One One". بمعنى آخر ، قم دائمًا بتقييم جودة الحلول الجديدة مقارنةً بالحل الأولي وليس مع الحل الحالي.
- temperature-decrease-is-linear : إذا كان true ، فإن الانخفاض من البداية إلى درجة حرارة النهاية خطي ، وإلا فهو أسي. الانخفاض الأسي هو المعيار في أدبيات الصلب المحاكاة ، ولكن ينصح بانخفاض خطي في ورقتنا.
- reheating : ما إذا كان لإعادة تزوير درجة الحرارة على فترات زمنية معينة.
- reheating-coefficient : بمقدار زيادة درجة الحرارة ، إذا كان reheating true .
- reheating-times : كم مرة لزيادة درجة الحرارة أثناء الجري.
- magic-number-exponent : ما يسمى "الرقم السحري" للتنفيذ الأصلي لـ Ropke و Pissinger (انظر المرجع أعلاه).
قبول العتبة
- start-threshold : عتبة في بداية الجري.
- end-threshold : عتبة في نهاية الجري.
- threshold-decrease-is-linear : ما إذا كانت العتبة تقلل خطيًا ( true ) أو بشكل كبير ( false ) بين القيم البدء والنهاية.
طوفان كبير
- initial-water-level-ratio : مضاعف بتكلفة الحل الأولي ، للحصول على مستوى المياه الأولي.
- water-level-decrease-pct : انخفاض النسبة المئوية لمستوى الماء ، في كل تكرار.
السفر إلى سجل
- start-deviation : الحد الأقصى للانحراف المسموح به في بداية المدى.
- end-deviation : الحد الأقصى للانحراف في نهاية الجري.
- deviation-decrease-is-linear : ما إذا كان الانحراف ينخفض خطيًا ( true ) أو بشكل كبير ( false ) بين القيم البدء والنهاية.
تسلق التل المتأخر
- list-size : حجم قائمة القبول المتأخرة.
- allow-non-worsening : ما إذا كنت ستقبل دائمًا حلًا جديدًا غير محكم.
طوفان عظيم غير خط
- initial-water-level-ratio : مضاعف بتكلفة الحل الأولي ، للحصول على مستوى المياه الأولي. gap-to-increase-water-level : فجوة العتبة لإعادة تزوير مستوى المياه. water-level-increase-pct : النسبة المئوية لفرق المحلول ، الذي يزداد به مستوى المياه خلال مراحل الزيادة. water-level-decrease-exp-factor : عامل أسي (دلتا في ورقتنا) لاستخدامه عند تقليل مستوى الماء.
أسوأ قبول
- start-probability : احتمال القبول في بداية التشغيل.
- end-probability : احتمال القبول في نهاية الجري.
- probability-decrease-is-linear : ما إذا كان الاحتمال ينخفض خطيًا ( true ) أو بشكل كبير ( false ) بين القيم البدء والنهاية.