Harmony Search Algorithm for Multi-objective Optimization Problem: Theory, Application and Case Studies

Abstract

Harmony search (HS) is one of the metaheuristic algorithms, which is developed from the behavior of musicians who trying to find the best aesthetic sound. The important attribute to metaheuristic is good solutions in a reasonable computational time. However, if we want a good answer, we have to find a proper conditions. Therefore, we studied the Harmony Search algorithm for traveling salesman problems (TSP) and Harmony Search algorithm for systematic planning for Surface Mount PCB Assembly.

In the first part, Harmony Search algorithm was applied to travelling salesman problem (TSP). TSP which is an NP-complete problem. It was solved by selecting the benchmark data sets (UK12, WG59 and SGB128) for the evaluations. Then, the encoding and decoding schemes are presented which is based on the amount of cities tested. Random values are represented by city codes. After that, the value is rearranged in ascending order. Subsequently, we has to find a parameter setting. In this study, we made use of statistical methods to find the appropriate parameter setting for travelling salesman problem. We found that the harmony memory consideration rate (HMCR) and iteration number (T) affect to the quality of results. In addition, we also confirmed that the large iteration number would not affect the development of the result.

In the second part, Harmony Search algorithm was applied to systematic planning for the Surface Mount PCB Assembly. The problem was formulated as multi-objective problem. We used a set of data with 71 electronic components. Each electronic component is applied to each city as same as traveling salesman problem. Then, the encoding and decoding methods are the same as we used in part 1. The parameter setting was found by using statistical methods. We found that the harmony memory consideration rate (HMCR) and iteration number (T) parameters had affected to the response, with the same results as shown in the first part. Furthermore, due to the planning of the Surface Mount PCB Assembly is a multi-objective problem, we have shown the performance of Harmony Search algorithm in order to construct Pareto front line. We showed that within 20,000 replicates it yields 5 solutions on the Pareto front. It accounted to 0.025 percent

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

เริ่มแรกทำการทดสอบการค้นหาความบรรสานกับปัญหาการเดินทางของพนักงานขาย ที่เป็นปัญหาลักษณะ NP-complete โดยเลือกชุดปัญหา UK12 WG59 และ SGB128 มาใช้สำหรับการทดสอบ จากนั้นดำเนินการสร้างวิธีการแปลงรหัส โดยทำการการสุ่มค่าตามจำนวนเมืองที่นำมาทดสอบ ซึ่งค่าที่ถูกสุ่มขึ้นจะถูกแทนรหัสเป็นเมืองแต่ละเมือง จากนั้นนำมาจัดลำดับจากน้อยไปหามาก เพื่อใช้เป็นค่าเริ่มต้นสำหรับการค้นหาความบรรสาน ต่อมาทางผู้วิจัยได้ดำเนินการหาพารามิเตอร์ที่เหมาะสมสำหรับการทดสอบในครั้งนี้ ด้วยวิธีการทางสถิติ พบว่าพารามิเตอร์ความน่าจะเป็นการใช้หน่วยความจำ (HMCR) และจำนวนการทำซ้ำ (T) ส่งผลต่อคำตอบอย่างมีนัยสำคัญ อีกทั้งพบว่าเมื่อจำนวนการทำซ้ำที่เพิ่มขึ้นมากเกินไปจะไม่ส่งผลในการพัฒนาคำตอบ

ต่อมาทำการทดสอบการค้นหาความบรรสานกับการวางแผนการประกอบแผงวงจรอิเล็คทรอนิกส์ซึ่งเป็นปัญหาหลายวัตถุประสงค์ โดยที่นี้จากผู้วิจัยได้ใช้ชุดข้อมูลที่มีจำนวนชิ้นส่วนอิเล็คทรอนิกส์ทั้งหมด 71 ชิ้นส่วน อีกทั้งนำลักษณะปัญหาการเดินทางของพนักงานขายมาประยุกต์ กำหนดให้ชิ้นส่วนอิเล็คทรอนิกส์แต่ละชนิดแทนเมืองแต่ละเมืองที่จะต้องเดินทาง จากนั้นทำการสร้างวิธีการแปลงรหัส ซึ่งในที่นี้จะใช้วิธีการเดียวกับปัญหาการเดินทางของพนักงานขาย จากนั้นทำการทดสอบหาพารามิเตอร์ที่ส่งผลต่อคำตอบด้วยวิธีการทางสถิติ พบว่ามีเพียงพารามิเตอร์ความน่าจะเป็นการใช้หน่วยความจำ (HMCR) และจำนวนการทำซ้ำ (T) ที่ส่งผลต่อคำตอบเช่นเดียวกับการทดสอบปัญหาการเดินทางของพนักงานขาย แต่อย่างไรก็ตามเนื่องจากการวางแผนการประกอบแผงวงจรอิเล็คทรอนิกส์เป็นปัญหาหลายวัตถุประสงค์ การสร้างคำตอบจะสร้างออกมาในลักษณะพาเรโต้ฟร้อน สำหรับการค้นหาความบรรสานในครั้งนี้ พบว่าเมื่อทำการทดสอบ 20,000 ครั้งจะมีคำตอบอยู่บนพาเรโต้ฟร้อน 5 คำตอบ หรือคิดเป็น 0.025 เปอร์เซ็น