The second and more important idea

The second and more important idea is to separate hard score and soft score. Here the hard score of a variable is the
change on the number (or total weight) of satisfied hard clauses caused by flipping the variable, and the soft score of a
variable is the change on the number (or total weight) of satisfied soft clauses caused by flipping the variable. By separating
hard score and soft score, the algorithm becomes more flexible, in the sense that it can pick the flipping variable according
to either hard score or soft score, or both, according to different situations.
The third idea is a variable selection heuristic based on hard score and soft score. The heuristic distinguishes three
different situations during the search, and uses hard score and soft score in different ways under each situation.
The three ideas mentioned above are used in developing a local search algorithm for PMS dubbed Dist, as it makes effective
use of Distinctions between hard and soft clauses. Results of the MaxSAT Evaluation 2014 as well as our experiments
show that Dist significantly outperforms previous local search solvers on all benchmarks from the MaxSAT Evaluation 2014,
with a remarkable improvement in terms of the number of “winning” instances on structured PMS benchmarks. We also
compare Dist with latest state-of-the-art complete solvers and a state-of-the-art portfolio solver on PMS benchmarks from
the MaxSAT Evaluation 2014. Experimental results show that Dist outperforms the complete solvers on random and crafted
benchmarks, while its performance on industrial instances is still considerably worse than complete solvers.
The aforementioned ideas and the Dist algorithm have been presented in [12], but in this article we add more experiments
and replace the complete solvers in our experiments with latest state-of-the-art ones. The following contributions
are new in this article.
In order to improve the performance of Dist on industrial PMS instances, we propose an initialization procedure called
PrioUP, which utilizes unit propagation and puts priority on hard unit clauses. The procedure produces a complete assignment,
which is then used as the initial assignment for the Dist solver. The resulting solver is called DistUP, and it significantly
improves Dist on industrial instances, although it still cannot rival complete solvers.
We also perform experimental analysis and additional investigations on the ideas in this work. In detail, we compare Dist
with its four alternative versions, and the experimental results illustrate the effectiveness of the ideas; more interestingly, all
alternatives based on separation of hard and soft score have better performance than previous local search algorithms, indicating
separation of hard and soft score is an essential technique and opens up a new direction for local search algorithms
for PMS (and also weighted PMS). We also study the effectiveness of the PrioUP procedure on Weighted PMS industrial
instances, and provide a discussion on the initialization procedure.
1.4. Structure of the paper
The remainder of this paper is organized as follows: some preliminary concepts are given in next section. We present
in detail three new local search ideas for PMS in Section 3, and present the Dist algorithm in Section 4. Then we present
the experimental study on Dist in Section 5. After that, we propose the PrioUP procedure, and apply it to improve Dist
in Section 6, where we also present experiments on the improved algorithm DistUP and a discussion on the initialization
procedure. Finally, we give some concluding remarks and directions for future research.

ผลลัพธ์ (ไทย) 1:

ความคิดสำคัญ และสองคือการ แยกนุ่มและหนักคะแนน นี่คือคะแนนยากของตัวแปรเปลี่ยนเลข (หรือน้ำหนักรวม) ของประโยคยากพอใจที่เกิดจากการพลิกตัวแปร และคะแนนอ่อนของการตัวแปรคือ การเปลี่ยนแปลงในหมายเลข (หรือน้ำหนักรวม) ของประโยคอ่อนพอใจที่เกิดจากการพลิกตัวแปร โดยการแยกยากและคะแนนนุ่ม อัลกอริทึมกลายเป็นความยืดหยุ่นมากขึ้น ในแง่ที่ว่า มันสามารถเลือกพลิกผันแปรตามหนักคะแนน หรือคะแนนนุ่ม หรือทั้ง สอง ตามสถานการณ์ต่าง ๆความคิดที่สามคือ วริเลือกตัวแปรที่อิงนุ่มและหนักคะแนน วริแยกสามสถานการณ์ต่าง ๆ ในระหว่างการค้น หา และใช้ยาก และคะแนนอ่อนในรูปแบบต่าง ๆ ภายใต้แต่ละสถานการณ์3 ไอเดียดังกล่าวข้างต้นจะใช้ในการพัฒนาอัลกอริทึมการค้นหาท้องถิ่น PMS ขนานข้าม มันทำให้มีประสิทธิภาพการใช้ความแตกต่างระหว่างข้อแข็ง และอ่อน ผล MaxSAT 2557 การประเมินตลอดจนการทดลองของเราแสดงว่า ข้ามอย่างมีประสิทธิภาพสูงกว่าก่อนหน้านี้ค้นหาท้องถิ่นแก้บนทั้งหมดมาตรฐานจากการประเมิน 2014 MaxSATมีการปรับปรุงที่โดดเด่นในแง่ของจำนวนของอินสแตนซ์ "ชนะ" ใน PMS โครงสร้างกำหนด เรายังเปรียบเทียบข้ามแก้สมบูรณ์ล่าสุดของศิลปะและมีผลงานศิลปะของ solver ใน PMS มาตรฐานจากประเมิน MaxSAT 2014 ผลการทดลองแสดงว่า ข้ามมีประสิทธิภาพสูงกว่าแก้สมบูรณ์แบบสุ่ม และออกแบบมาเพื่อกำหนด ในขณะที่ประสิทธิภาพการทำงานบนอินสแตนซ์อุตสาหกรรมยังคงมากเลวร้ายยิ่งกว่าแก้สมบูรณ์ความคิดดังกล่าวข้างต้นและอัลกอริทึมข้ามได้เสนอใน [12], แต่ในบทความนี้ เราเพิ่มการทดลองเพิ่มเติมและแทนที่แก้เสร็จสมบูรณ์ในการทดลองของเรา มีล่าสุดรัฐ-ของ-the-art คน การจัดสรรดังต่อไปนี้ได้ใหม่ในบทความนี้เพื่อปรับปรุงประสิทธิภาพของข้ามบนอินสแตนซ์ของ PMS อุตสาหกรรม เรานำเสนอขั้นตอนการเตรียมใช้งานที่เรียกว่าPrioUP ซึ่งใช้หน่วยเผยแพร่ และทำให้ความสำคัญในประโยคหน่วยยาก กระบวนการผลิตการกำหนดสมบูรณ์นอกจากนี้ซึ่งจากนั้นจะใช้เป็นการกำหนดเริ่มต้นสำหรับ solver ข้าม Solver ผลลัพธ์เรียกว่า DistUP และมันมากปรับปรุงข้ามบนอินสแตนซ์อุตสาหกรรม แม้ว่ามันยังไม่คู่แข่งแก้สมบูรณ์เราจะทำการทดลองวิเคราะห์และสอบสวนเพิ่มเติมบนความคิดในการทำงานนี้ รายละเอียด เราเปรียบเทียบข้ามกับรุ่นอื่นของสี่ และผลการทดลองแสดงให้เห็นถึงประสิทธิภาพของความคิด ทุกอย่างน่าสนใจทางเลือกที่อิงการแยกของแข็ง และอ่อนมีประสิทธิภาพที่ดีกว่าก่อนหน้าท้องถิ่นค้นหาอัลกอริทึม บ่งชี้แยกของแข็ง และอ่อนเป็นเทคนิคจำเป็น และเปิดขึ้นทิศทางใหม่ของอัลกอริทึมค้นหาท้องถิ่นสำหรับ PMS (และยังถ่วงน้ำหนัก PMS) เรายังศึกษาประสิทธิผลของกระบวนการ PrioUP ในอุตสาหกรรมถัว PMSอินสแตนซ์ และมีการอภิปรายในขั้นตอนการเตรียมใช้งาน1.4 โครงสร้างของกระดาษส่วนที่เหลือของเอกสารนี้ถูกจัดเป็นดังนี้: แนวคิดเบื้องต้นบางอย่างได้ในส่วนถัดไป เรานำเสนอในรายละเอียดความคิดค้นหาถิ่นใหม่สามสำหรับ PMS ในส่วนที่ 3 และปัจจุบันอัลกอริทึมข้ามในส่วนที่ 4 จากนั้น เรานำเสนอการศึกษาทดลองในข้ามในส่วนที่ 5 หลังจากนั้น เรานำเสนอขั้นตอนการ PrioUP และนำไปใช้ในการปรับปรุงข้ามในมาตรา 6 ซึ่งเรายังนำเสนอการทดลองบนอัลกอริทึมที่ดีขึ้น DistUP และสนทนาในการเริ่มต้นขั้นตอนนี้ ในที่สุด เราให้บางสรุปเหตุและเส้นทางสำหรับการวิจัยในอนาคต

ผลลัพธ์ (ไทย) 2:

ความคิดที่สองและที่สำคัญมากคือการแยกคะแนนอย่างหนักและคะแนนนุ่ม นี่คะแนนอย่างหนักของตัวแปรคือ
การเปลี่ยนแปลงที่หมายเลข (หรือน้ำหนักรวม) ของคำสั่งอย่างหนักมีความพึงพอใจที่เกิดจากการพลิกตัวแปรและคะแนนนุ่มของ
ตัวแปรคือการเปลี่ยนแปลงที่หมายเลข (หรือน้ำหนักรวม) ของคำสั่งที่อ่อนนุ่มมีความพึงพอใจ เกิดจากการพลิกตัวแปร โดยแยก
คะแนนอย่างหนักและคะแนนนุ่มอัลกอริทึมจะกลายเป็นความยืดหยุ่นมากขึ้นในแง่ที่ว่ามันสามารถเลือกตัวแปรพลิกตาม
อย่างใดอย่างหนึ่งคะแนนแข็งหรือคะแนนนุ่มหรือทั้งสองตามสถานการณ์ที่แตกต่างกัน.
ความคิดที่สามคือการแก้ปัญหาการเลือกตัวแปรตาม กับคะแนนอย่างหนักและคะแนนนุ่ม แก้ปัญหาสามแยก
สถานการณ์ที่แตกต่างกันในระหว่างการค้นหาและใช้คะแนนอย่างหนักและคะแนนนุ่มในรูปแบบที่แตกต่างกันในแต่ละสถานการณ์.
สามความคิดดังกล่าวข้างต้นถูกนำมาใช้ในการพัฒนาอัลกอริทึมการค้นหาในท้องถิ่นสำหรับ PMS ขนานนาม Dist เนื่องจากทำให้มีประสิทธิภาพ
การใช้งานของความแตกต่างระหว่าง คำสั่งแข็งและอ่อน ผลของการประเมินผล MaxSAT 2014 เช่นเดียวกับการทดลองของเรา
แสดงให้เห็นว่ามีประสิทธิภาพดีกว่าอย่างมีนัยสำคัญ Dist แก้การค้นหาในท้องถิ่นก่อนหน้านี้เกี่ยวกับการวัดทั้งหมดจาก MaxSAT ประเมินผลปี 2014
มีการปรับปรุงที่โดดเด่นในแง่ของจำนวน "ชนะ" อินสแตนซ์บนโครงสร้างมาตรฐาน PMS นอกจากนี้เรายัง
เปรียบเทียบ Dist ล่าสุดรัฐของศิลปะแก้ที่สมบูรณ์และรัฐของศิลปะผลงานแก้กับการวัดประสิทธิภาพ PMS จาก
ผลการทดลอง MaxSAT ประเมินผลปี 2014 แสดงให้เห็นว่า Dist มีประสิทธิภาพดีกว่าแก้ที่สมบูรณ์ในการสุ่มและฝีมือ
มาตรฐาน, ในขณะที่ผลการดำเนินงานของตนในกรณีอุตสาหกรรมยังคงเป็นอย่างมากเลวร้ายยิ่งกว่าแก้สมบูรณ์.
ความคิดดังกล่าวข้างต้นและขั้นตอนวิธีการ Dist ได้รับการนำเสนอใน [12] แต่ในบทความนี้เราจะเพิ่มการทดลองมากขึ้น
และเปลี่ยนแก้สมบูรณ์ในการทดลองของเราด้วยล่าสุดรัฐของ คน -The ศิลปะ ผลงานดังต่อไปนี้
เป็นเรื่องใหม่ในบทความนี้.
เพื่อที่จะปรับปรุงประสิทธิภาพการทำงานของ Dist ในกรณี PMS อุตสาหกรรมเราเสนอขั้นตอนการเริ่มต้นที่เรียกว่า
PrioUP ซึ่งใช้การขยายพันธุ์และทำให้หน่วยให้ความสำคัญกับคำสั่งหน่วยยาก ขั้นตอนการผลิตที่ได้รับมอบหมายเสร็จสมบูรณ์
ซึ่งจะใช้แล้วเป็นการกำหนดเริ่มต้นสำหรับการแก้ Dist แก้ที่เกิดเรียกว่า DistUP และมันอย่างมีนัยสำคัญ
ช่วยเพิ่ม Dist ในกรณีอุตสาหกรรมแม้ว่ามันจะยังไม่สามารถแก้คู่แข่งสมบูรณ์.
นอกจากนี้เรายังดำเนินการวิเคราะห์การทดลองและการตรวจสอบเพิ่มเติมเกี่ยวกับความคิดในงานนี้ ในรายละเอียดเราเปรียบเทียบ Dist
กับสี่รุ่นทางเลือกของตนและผลการทดลองแสดงให้เห็นถึงประสิทธิภาพของความคิดนั้น น่าสนใจมากขึ้นทุก
ทางเลือกบนพื้นฐานของการแยกของคะแนนแข็งและอ่อนมีประสิทธิภาพที่ดีกว่าขั้นตอนวิธีการค้นหาในท้องถิ่นก่อนหน้านี้แสดงให้เห็น
การแยกของคะแนนแข็งและอ่อนเป็นเทคนิคที่จำเป็นและเปิดขึ้นในทิศทางใหม่สำหรับขั้นตอนวิธีการค้นหาในท้องถิ่น
สำหรับ PMS (และยังถ่วงน้ำหนัก PMS ) นอกจากนี้เรายังศึกษาประสิทธิผลของขั้นตอนในการถ่วงน้ำหนัก PrioUP PMS อุตสาหกรรม
กรณีและให้การอภิปรายเกี่ยวกับขั้นตอนการเริ่มต้นได้.
1.4 โครงสร้างของกระดาษ
ที่เหลือของบทความนี้จะจัดเป็นดังนี้: บางแนวคิดเบื้องต้นจะได้รับในส่วนถัดไป เรานำเสนอ
ในรายละเอียดความคิดที่สามการค้นหาในท้องถิ่นใหม่สำหรับ PMS ในมาตรา 3 และนำเสนอขั้นตอนวิธี Dist ในมาตรา 4 แล้วเรานำเสนอ
การศึกษาทดลอง Dist ในมาตรา 5 หลังจากที่เรานำเสนอขั้นตอน PrioUP และนำไปใช้ในการปรับปรุง Dist
ในมาตรา 6 ที่เรายังทดลองอยู่บน DistUP ขั้นตอนวิธีการที่ดีขึ้นและการอภิปรายเกี่ยวกับการเริ่มต้นเป็น
ขั้นตอน สุดท้ายเราให้ข้อสังเกตบางสรุปและทิศทางการวิจัยในอนาคต

ผลลัพธ์ (ไทย) 3:

ความคิดที่สองและที่สำคัญคือการแยกและคะแนนคะแนนมากนุ่ม ที่นี่คะแนนอย่างหนักของตัวแปรคือเปลี่ยนเบอร์ ( หรือน้ำหนักรวมของพอใจอย่างหนักส่วนที่เกิดจากการพลิกแปร และนุ่ม คะแนนของตัวแปร คือ การเปลี่ยนแปลงจำนวนหรือน้ำหนักรวมของพอใจอ่อนข้อเกิดจากการพลิกแปร โดยการคะแนนและคะแนนอ่อนแข็ง ขั้นตอนวิธีการ กลายเป็นมีความยืดหยุ่นมากขึ้น ในแง่ที่ว่ามันสามารถเลือกสำหรับตัวแปรตามเพื่อให้คะแนนยาก หรือคะแนนที่นุ่ม หรือทั้งสอง ตามสถานการณ์ที่แตกต่างกันความคิดที่สาม คือ การเลือกตัวแปรแบ่งตามคะแนนยากและคะแนนที่อ่อนนุ่ม การแบ่งแยกสามสถานการณ์ต่าง ๆ ในการค้นหา และใช้ยาก คะแนน และคะแนนอ่อนในวิธีที่แตกต่างกันในแต่ละสถานการณ์ .สามความคิดที่กล่าวถึงข้างต้นจะใช้ในการพัฒนาอัลกอริทึมการค้นหาในท้องถิ่นสำหรับ PMS ขนานนาม Dist , ทำให้มีประสิทธิภาพการใช้ความแตกต่างระหว่างหนักเบาและอนุประโยค ผล maxsat การประเมิน 2014 เช่นเดียวกับการทดลองของเราแสดงให้เห็นว่ามีการแก้โปรย Dist ก่อนหน้านี้ท้องถิ่นบนมาตรฐานทั้งหมดจาก maxsat การประเมิน 2014 ,ด้วยการปรับปรุงที่โดดเด่นในแง่ของจำนวนของ " ชนะ " อินสแตนซ์ในโครงสร้าง PMS มาตรฐาน . นอกจากนี้เรายังเปรียบเทียบกับรัฐ - of - the - art Dist ล่าสุดสมบูรณ์แก้และแก้ผลงานรัฐ - of - the - art ใน PMS มาตรฐานจากการ maxsat การประเมิน 2014 ผลการทดลองแสดงให้เห็นว่า Dist มีประสิทธิภาพดีกว่าแก้เสร็จและร่างแบบสุ่มมาตรฐาน ในขณะที่ประสิทธิภาพในอินสแตนซ์ของอุตสาหกรรมยัง มากยิ่งกว่าแก้สมบูรณ์ความคิดดังกล่าวและอัลกอริทึมได้ถูกนำเสนอในจังหวัดนครราชสีมา [ 12 ] แต่ในบทความนี้เราจะเพิ่มการทดลองมากขึ้นและแทนที่แก้เสร็จสมบูรณ์ในการทดลองของเราที่ทันสมัยล่าสุด เขียนต่อไปนี้ใหม่ในบทความนี้เพื่อปรับปรุงประสิทธิภาพของอุตสาหกรรม Dist PMS อินสแตนซ์ เราเสนอให้มีการเริ่มต้นกระบวนการที่เรียกว่าprioup ซึ่งใช้ขยายพันธุ์หน่วยและทำให้ความข้อหน่วยที่หนัก กระบวนการผลิตงานเสร็จสมบูรณ์ซึ่งเป็นที่ใช้งานเบื้องต้นสำหรับ Dist แก้ ผลแก้เรียกว่า distup และมันอย่างมากปรับปรุง Dist บนอินสแตนซ์อุตสาหกรรม แม้ว่าจะยังไม่สามารถตีเสมอให้แก้ .นอกจากนี้เรายังดำเนินการวิเคราะห์ทดลอง และสอบสวนเพิ่มเติมเกี่ยวกับความคิดในงานชิ้นนี้ ในรายละเอียด เราเปรียบเทียบ จังหวัดนครราชสีมากับทางเลือกของ 4 รุ่น และผลการทดลองแสดงให้เห็นว่าประสิทธิภาพของแนวคิด น่าสนใจมากขึ้นทุกทางเลือกขึ้นอยู่กับการแยกยากและคะแนนอ่อนมีประสิทธิภาพดีขึ้นกว่าเดิมแสดงขั้นตอนวิธีการค้นหาท้องถิ่นการแยกหนักเบาและคะแนนเป็นเทคนิคที่จำเป็นและเปิดทิศทางใหม่สำหรับขั้นตอนวิธีการค้นหาท้องถิ่นสำหรับ PMS ( และ PMS ถ่วงน้ำหนัก ) นอกจากนี้เรายังศึกษาประสิทธิผลของกระบวนการ prioup ใน PMS หนักอุตสาหกรรมกรณี และให้อภิปรายเกี่ยวกับขั้นตอนการเริ่มต้น .1.4 . โครงสร้างของกระดาษส่วนที่เหลือของบทความนี้คือการจัดดังนี้ : แนวคิดเบื้องต้นบางอย่าง จะได้รับ ในส่วน เราปัจจุบันในรายละเอียดสามใหม่ค้นหาท้องถิ่น แนวคิด PMS ในมาตรา 3 และเสนอ Dist ขั้นตอนวิธีในมาตรา ๔ งั้นเราปัจจุบันการศึกษาทดลองในจังหวัดนครราชสีมา ในมาตรา 5 หลังจากที่เรานำเสนอขั้นตอน prioup และใช้มันเพื่อปรับปรุง Distในมาตรา 6 ที่เรานำเสนอการทดลองเกี่ยวกับวิธีการที่ดีขึ้น distup และอภิปรายเกี่ยวกับเริ่มต้นขั้นตอน สุดท้ายเราให้สรุปข้อสังเกตและทิศทางการวิจัยในอนาคต