School of Science and Technology 科技學院
Computing Programmes 電腦學系
| Programme | Bachelor of Science with Honours in Internet Technology |
| Supervisor | Dr. Vanessa Ng |
| Areas | Algorithms |
| Year of Completion | 2016 |
| Award Received | First Runner-Up, IEEE Computational Intelligence Chapter FYP Competition 2016 |
“Multi-Objective Particle Swarm Optimization” (MOPSO) is one of the long-term developed algorithm technique in the area of multi-objective optimization. However, the solution set comes from original MOPSO algorithm is usually not the best in solving the complex multi-objective problems (MOP). Multi-Objective Evolutionary Algorithm based on decomposition (MOEA/D) has been proposed for a decade in solving complex MOP by decomposing it into several single-objective problems. MOEA/D is widely considered as an ideal substitution of MOPSO algorithm.
MOEA/D-AGR is one of the improved algorithm introduced recently to substitute the original replacement scheme in MOEA/D with a new adaptive global replacement (GR) scheme so that the neighborhood replacement size Tr is increased among the generation to achieve the shifting of focus from solution diversity to convergence. However, the new replacement scheme only concerns the one-way convergence of the objective solutions among all sub-problems. It is hard to re-achieve the solution diversity once the algorithm reaches another steeper landscape of solution from a flatten one while it is focusing on convergence. In this final year project, the original MOEA/D-AGR algorithm will be improved by alternating the adaptive mechanism to handle the case mentioned above.
To improve the existing MOEA/D-AGR algorithm performance, several objectives have been defined here to clarify the way to achieve the aim of this research project.
To adapt variable fitness landscapes, a new AGR scheme with improved adaptive approach is proposed in this paper where the value of Tr is changed adaptively if there is an increase in average change of objective values among all the solutions of sub-problems between two consecutive generations. The main purpose of this approach is to prolong the whole period in increasing the Tr value based on original Sigmoid scheme in AGR, so that it enhances the diversity of the approximated solutions during the generations once the slope of the fitness landscape of the MOP becomes steeper again.
Moreover, to compensate the delayed convergence under the new AGR scheme, local searching is used here to look for new solutions nearby. Simulated Annealing (SA) (Kirkpatrick et al., 1983) is chosen here and it will be invoked for those sub-problems with any unchanged solution values after a predefined number of generations (i.e., the solution of the sub-problem is converged). To make an appropriate arrangement of SA in the same time that does not affect the diversity of the original solutions, Fuzzy Logic is used here to control the frequency of SA operated on those sub-problems which have been kept idle after corresponding number of generations.
As mentioned, the value of Tr is changed based on the level of average changed in objective values among all the sub-problems. In each generation, the change of an objective solution value xi of each sub-problem i can be simply calculated by the Euclidean Distance:
where xij,k – xij,k–1 means the difference of solution value of objective j under two continuous generations k and k – 1.
The average change of objective value from all sub-problems X is then calculated on next step. One of the target values Xavg representing an average value of X among each generation will then be updated. Another target value Xmax is used to records the maximum Xavg value appeared during the generation. The obtained values Xavg and Xmax are the main key in coordinating the change of Tr value and the control criteria in Fuzzy Logic mentioned later.
Considering the Sigmoid formula of the original MOEA/D-AGR, the value of Tr is changed depending on the ratio of current iteration to the maximum times of iteration (i.e.: k/K). Small ratio of k/K represents a high value of Tr for diversity. To prolong the period of the increasing Tr, it is proposed in this paper that the value of K should be enlarged so that the ratio of k/K and Tr calculated will be reduced to a certain value. The following equation shows how the value of K is alternated according to the level of increment in Xavg over two consecutive generations k and k – 1 if Xavg, k – Xavg, k – 1 > 0:
where µ is the parameter limits the maximum increment in percentage of value K during each generation in order to avoid over-elongation of the period. It is noted that the actual total number of generations does not change. Since the Xavg value may increase continuously for several generations, a negligible change on Xavg value may result in any unexpected effect. A sufficient long period of generations is only taken into consideration for significantly increasing of the K value. That's why the µ value should not be too large.
To implement a multi-objective version of the SA algorithm, the backbone of Evolutionary Multi-Objective Simulated Annealing (EMOSA) algorithm introduced by Li and Landa-Silva is referenced and simplified here (Li and Landa-Silva, 2008). The main steps including population evolution and change of temperature t is extracted here. At the beginning, t is assigned as initial temperature t0. For each of the sub-problems i in the queue of local searching, a new solution x' will be generated by mutation and the solution x' is compared to the current best solution xibest by using the original decomposition method in MOEA/D-AGR. Replacement is processed if gte(x') < gte(xibest). In addition, the x' will also replace the current candidate sub-problem i under the probability of P(x, x', t) where
The procedure of mutation and replacement will be repeated for L times as the number of local searching movement for each sub-problem between two consecutive temperature levels. Finally, the value of t will be decreased according to the cooling level t'. The whole SA process will restart until t < tmin.
Referring to the performance on the series of two objectives MOP problems, which are non-linear of the inter-variable dependency, the performance of those new MOEA/D-AGR algorithms, are found to be compared hardly. The experiment result data shows that the variance of results among the original and two new MOEA/D-AGR algorithms are similar majorly in entropy value. It shows that the new mechanism of enhancing the solution diversity in the proposed new algorithm might not take much effort in MOP series problems.
From the result graph shown in Figure a and b shows that the original and the new MOEA/D-AGR algorithm had already approximate the whole uniform distribution of Pareto Front solution. In other words, only the convergence be the one criteria left in comparing their performance. The proposed new MOEA/D-AGR algorithm with Local Searching gave the best performance with majorly lowest IGD value except MOP1 and MOP3, where which without Local Searching yielded the slightly worse quality of Pareto Front solution. In MOP1, the algorithm with the lowest IGD value was MOEA/D-GR, which its performance among other MOP algorithms were not stable. The algorithm with the second lowest IGD value was the original MOEA/D-AGR, which the IGD value is very similar to that of the proposed new MOEA/D-AGR value with Local Searching. Only the result of MOP3 showed that the new algorithms could not take advantage here. For the MOP6 and MOP7 which have the characteristic of non-convex and multi-model, the both new MOEA/D-AGR algorithms yielded the IGD values which are significantly better than that of the original MOEA/D-AGR algorithm. Note that the MOEA/D-DE could not make any Pareto Front solution with approximating the distribution of real Pareto Front in MOP3 and MOP7. In general, the results above showed that the new MOEA/D-AGR with Local Searching usually could obtain more approximated Pareto Front solutions in the series MOP problems than the original one.
Lastly, the whole series of three-objective problems DTLZ consists a larger solution space domain with three-dimension. The ability of seeking a more diverse and approximated Pareto Front is much more challenged in the series of DTLZ problem. The result of the proposed new MOEA/D-AGR algorithm with Local Searching yielded the averagely best performance referring to the IGD and Entropy value ranking, where that without Local Searching could yield a similar result. Comparing these new algorithms to original MOEA/D-AGR, it was found that the performance are similar majorly in DTLZ1, DTLZ2, DTLZ3 which have the uniform 3-dimension Pareto Front design. In DTLZ4 which more local minimum are allocated in the solution space, the diversity of solution yield by new purposed MOEA/D-AGR algorithms were much better than that of original MOEA/D-AGR, but the solution convergence of them were slightly worse according to the IGD value. For DTLZ7 which has the discontinuous Pareto Front hyperplane, both new algorithms could yield the solution with better convergence and diversity than that of original MOEA/D-AGR algorithm. It should be conclude that the new algorithms takes more advantage in discontinuous solution space, in same time the selection of Local Searching operation still performing a balance between diversity and convergence of solution in DTLZ7.
The following future works will focus on performance improving and investigate the possibility in tackling more complex problem. To solve the time-consuming problem in Local Searching, the Simulated Annealing algorithm should be optimized for this new algorithm used. One of the possible solution is to adaptive change the parameter of Simulated Annealing algorithm like the initial temperature so that the useless Local Searching effort can be reduced. Another possible solution is to use another advance Local Searching algorithm like Tabu Search and Particle Swarm Optimization with better local searching ability. Several preparation and evaluation works will be planned in future.
In addition, the algorithm can be tested for any possibility under the many-objective optimization problem, which more than three objectives have to be optimized. Many-objective Optimization consists a much higher level of solution space domain. The management of objective searching effort are well investigated and discussed. This algorithm may try to optimize in many-objective solution space and the searching can shift adaptively the focus between convergence and diversity upon the change of fitness landscape in different set of objectives.
Copyright Tam Hiu Hin and Vanessa Ng 2016
Jonathan handles all external affairs include business development, patents write up and public relations. He is frequently interviewed by media and is considered a pioneer in 3D printing products.
After graduating from OUHK, Krutz obtained an M.Sc. in Engineering Management from CityU. He is now completing his second master degree, M.Sc. in Biomedical Engineering, at CUHK. Krutz has a wide range of working experience. He has been with Siemens, VTech, and PCCW.
Hugo Leung Wai-yin, who graduated from his four-year programme in 2015, won the Best Paper Award for his ‘intelligent pill-dispenser’ design at the Institute of Electrical and Electronics Engineering’s International Conference on Consumer Electronics – China 2015.
The pill-dispenser alerts patients via sound and LED flashes to pre-set dosage and time intervals. Unlike units currently on the market, Hugo’s design connects to any mobile phone globally. In explaining how it works, he said: ‘There are three layers in the portable pillbox. The lowest level is a controller with various devices which can be connected to mobile phones in remote locations. Patients are alerted by a sound alarm and flashes. Should they fail to follow their prescribed regime, data can be sent via SMS to relatives and friends for follow up.’ The pill-dispenser has four medicine slots, plus a back-up with a LED alert, topped by a 500ml water bottle. It took Hugo three months of research and coding to complete his design, but he feels it was worth all his time and effort.
Hugo’s public examination results were disappointing and he was at a loss about his future before enrolling at the OUHK, which he now realizes was a major turning point in his life. He is grateful for the OUHK’s learning environment, its industry links and the positive guidance and encouragement from his teachers. The University is now exploring the commercial potential of his design with a pharmaceutical company. He hopes that this will benefit the elderly and chronically ill, as well as the society at large.
Soon after completing his studies, Hugo joined an automation technology company as an assistant engineer. He is responsible for the design and development of automation devices. The target is to minimize human labor and increase the quality of products. He is developing products which are used in various sections, including healthcare, manufacturing and consumer electronics.
| Course Code | Title | Credits | |
|---|---|---|---|
| COMP S321F | Advanced Database and Data Warehousing | 5 | |
| COMP S333F | Advanced Programming and AI Algorithms | 5 | |
| COMP S351F | Software Project Management | 5 | |
| COMP S362F | Concurrent and Network Programming | 5 | |
| COMP S363F | Distributed Systems and Parallel Computing | 5 | |
| COMP S382F | Data Mining and Analytics | 5 | |
| COMP S390F | Creative Programming for Games | 5 | |
| COMP S492F | Machine Learning | 5 | |
| ELEC S305F | Computer Networking | 5 | |
| ELEC S348F | IOT Security | 5 | |
| ELEC S371F | Digital Forensics | 5 | |
| ELEC S431F | Blockchain Technologies | 5 | |
| ELEC S425F | Computer and Network Security | 5 |
| Course Code | Title | Credits | |
|---|---|---|---|
| ELEC S201F | Basic Electronics | 5 | |
| IT S290F | Human Computer Interaction & User Experience Design | 5 | |
| STAT S251F | Statistical Data Analysis | 5 |
| Course Code | Title | Credits | |
|---|---|---|---|
| COMPS333F | Advanced Programming and AI Algorithms | 5 | |
| COMPS362F | Concurrent and Network Programming | 5 | |
| COMPS363F | Distributed Systems and Parallel Computing | 5 | |
| COMPS380F | Web Applications: Design and Development | 5 | |
| COMPS381F | Server-side Technologies and Cloud Computing | 5 | |
| COMPS382F | Data Mining and Analytics | 5 | |
| COMPS390F | Creative Programming for Games | 5 | |
| COMPS413F | Application Design and Development for Mobile Devices | 5 | |
| COMPS492F | Machine Learning | 5 | |
| ELECS305F | Computer Networking | 5 | |
| ELECS363F | Advanced Computer Design | 5 | |
| ELECS425F | Computer and Network Security | 5 |
