ดาวน์โหลดการ adaptive large neighbourhood search adaptive large neighbourhood search

adaptive large neighbourhood search

ซอร์สโค้ดอื่น ๆ

v0.2

ดาวน์โหลด

การค้นหาพื้นที่ใกล้เคียงขนาดใหญ่ที่ปรับตัวได้

นี่คือการใช้งาน C ++ เฉพาะของการใช้งาน (คู่ขนาน) อัลกอริทึมการค้นหาเพื่อนบ้านขนาดใหญ่ที่ปรับตัวได้ซึ่งคิดค้นโดย Ropke และ Pisinger รหัสนี้ขึ้นอยู่กับการใช้งานดั้งเดิมที่ Stefan Ropke ได้แบ่งปันกับฉันอย่างอ่อนโยน

เฟรมเวิร์ก 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 }
}

การดำเนินการนี้ยังรวมถึงเกณฑ์การยอมรับหลายอย่างเนื่องจากพวกเขาได้รับการแนะนำในบทความการเปรียบเทียบเกณฑ์การยอมรับสำหรับ metaheuristic การค้นหาพื้นที่ใกล้เคียงขนาดใหญ่ที่ปรับตัวได้ (preprint) หากคุณใช้ซอฟต์แวร์นี้โปรดอ้างถึงบทความสุดท้ายนี้ดังนี้:

 @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)
subclass ของ 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 ซึ่งส่งคืน 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 : ขีด จำกัด อย่างหนักในเวลา CPU ของอัลกอริทึม
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 : basename สำหรับไฟล์ผลลัพธ์

พารามิเตอร์การยอมรับ

ในต่อไปนี้เราแสดงรายการพารามิเตอร์ที่สัมพันธ์กับเกณฑ์การยอมรับ เราขอเรียกร้องให้ผู้ใช้อ้างถึงเอกสารเกณฑ์การยอมรับเพื่อทำความเข้าใจบทบาทของแต่ละพารามิเตอร์และคำศัพท์ที่ใช้ด้านล่าง กระดาษยังนำเสนอพารามิเตอร์ที่ได้รับการปรับแต่งที่ดีที่สุดในการแก้ไขปัญหาที่หลากหลาย

การยอมรับการหลอมแบบจำลอง
- init-ratio-50p : โซลูชันที่เลวร้ายยิ่งกว่าที่ได้รับการยอมรับด้วยความน่าจะเป็น 50% ที่จุดเริ่มต้นของการวิ่ง
- end-ratio-50p : การแก้ปัญหาที่เลวร้ายยิ่งกว่าที่ได้รับการยอมรับด้วยความน่าจะเป็น 50% เมื่อสิ้นสุดการวิ่ง
- end-ratio-50p-refers-to-initial : ถ้าตั้งค่าเป็น true ในคำอธิบายของ end-ratio-50p แทนที่ "ปัจจุบันหนึ่ง" ด้วย "เริ่มต้น" กล่าวอีกนัยหนึ่งจะประเมินคุณภาพของโซลูชันใหม่เสมอเมื่อเทียบกับโซลูชันเริ่มต้นและไม่ได้อยู่กับโซลูชันปัจจุบัน
- 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 ) ระหว่างค่าเริ่มต้นและสิ้นสุด