School of Science and Technology 科技學院
Computing Programmes 電腦學系
| Programme | Bachelor of Computing with Honours in Internet Technology |
| Supervisor | Prof. Vanessa Ng |
| Areas | Algorithms |
| Year of Completion | 2020 |
| Award | Merit of IEEE (HK) Computational Intelligence Chapter 17th FYP Competition |
There are many different kinds of evolutionary algorithms to solve multi-objective problems, and multi-objective particle swarm optimization is one of the famous heuristic searching techniques. Although some optimization problems can reduce to a single-objective optimization by dimensionality reduction, most optimization problems are difficult to convert into a single-objective, and the demands of MOPs increased.
In this project, we are going to study and improve the state-of-the-art MOPSO algorithms. The proposed algorithm was based on the competitive mechanism MOPSO that guides the particles by the current population. We aim to achieve better performance that balances between exploration and exploitation of the whole swarm, avoid premature convergence, and maintain a well-distributed Pareto front. The details of CMOPSO and the proposed algorithm will be discussed in detail later.
Moreover, the proposed algorithm evaluated with the other famous MOPSO algorithms in inverted generational distance indicators in popular standard benchmarks tests problems. The accuracy of the real solutions and diversity are important measurements of the proposed algorithm. At last, the proposed algorithm was applied to the signalized traffic problem to optimize the effective green time of each phase in real-world problems.
The major objective of this project consists of four parts:
Background
The proposed MCMOPSO algorithm aims to resolve these constraints by applying multi-competition. The algorithm constructs three main complements, for instance, new leader selection, analysis inertia weight of the equation, and conclusion of the proposed algorithm.
Multi-Competition Leader Selection
There are a few steps for the new leader selection. First, we determine the numbers of the selected elite particles and determine whether the smallest or the largest angle. Second, the elite particles are selected randomly within the pre-defined numbers. Third, we calculate each angle between selected elite particles and the particle to be updated by two vectors from three coordinates with the origin, selected elite particles, and the particle to be updated. Next, we discover the winner by the smallest angle or the largest angle from the sets of randomly selected elite particles.
We divide the new leader selection into three cases to enhance the efficiency that more beneficial to convergence and distributed Pareto optimal solutions. If the particle to be updated is the members of the leader set, the particle update by the smallest angle between two randomly selected elite particles. It enables the updated particle always towards other elite particles because selected elite particles may be equivalent to the updated particle.
Balance between Exploration and Exploitation
The inertia weight plays an important role in the previous velocity, which determines the ability to explore regions in the search space. When the velocity too high, it may skip the global optimum. When the velocity is too low, it may be stuck at a local optimum. Under this consideration, we set various weight parameters ranged from zero to one to determine the proper inertia weight in all the overall thirty-seven test problems. Based on the above discussions, the modified equation for updating velocities and positions of particles are:
where W is a parameter for the inertia weight R1 Vi. The value of W is needed to be investigated carefully as it affects the new velocity of the particles. As a result, an extensive investigation is conducted by varying the values of W.
Framework with External Archive
The MC leader selection enhances the convergence speed and the diversity by comparing the nearest or farthest angles between the particle to be updated and several randomly selected elite particles. Also, we analyze the effect of inertia weight to set a balance between the local and global search by decreasing the inertia weight from zero to one for each 0.1 distribution to observe the results as compared with the original algorithm..
In the CMOPSO algorithm, the loss of historical information may happen in environment selection that the non-dominated solution may no longer exist. The archive is to solve this issue. The particles are guided by the current swarm resulting in fast convergence speed. We adopted the external archive of crowding distance to store the solutions that can enhance the distribution of the found solutions.
Figure 2: Algorithm of Proposed Algorithm (MCMOPSO)
The size of the external archive is 10 percent of the population size to store the previous top crowding distance found solutions so as to maintain the small amount of external archive could avoid premature convergence. If the framework without the archive, the offspring cannot fly to the historical information after some non-dominated solutions truncated. Under this improvement, the historically found solutions may be more beneficial than the current particles, which could guide the particles to the top crowding distance to obtain a set of well-distributed Pareto optimal solutions.
After combining these improvements, the proposed algorithm takes advantage of these components and shown in algorithm 2 (fig.2).
The proposed algorithm was applied to the signalized traffic congestion real-world problem. The effective green time of each phase was optimized by the proposed algorithm to minimize the average vehicle delay and stops frequency per vehicle based on the actual traffic flow. The trade-off solution can be chosen by the decision- maker that objectives of average vehicle delay and stop frequency conflict with each other. The proposed algorithm was performed better than other MOPSO for the signalized traffic problem in terms of hypervolume.
Hypervolume (HV) measures the convergence and diversity of the discovered solutions. One main advantage of using HV is that prior knowledge of the true Pareto front is not required, which is suitable for real-world problems. The metric is defined as:
Figure 3: Measurement of Hypervolume Indicator
Figure 3 shows the idea of hypervolume with the reference point in bi-objective. Larger of the HV value indicates the better of the obtained solutions in terms of convergence and diversity.
Table 1: Reference Point on difference intersection
Table 2: Performance comparison for Intersection model on mean HV
Figure 4: Relations between the Cycle Time and Average Delay
Figure 5: Relations between the Cycle Time and Stop Frequency
Moreover, we observed the trend of the delay and stop frequency that affects the cycle time in figure 4 to 5. The increase in the cycle time will lead to an increment in the average vehicle delay and a drop in vehicle stop frequency. Oppositely, the decrease in the cycle time will direct to a reduction in the average vehicle delay and raise in the vehicle stop frequency. The objective of minimizing the delay and stops both are conflict with each other. For the intersection, we can obtain a lower average control delay with higher-stop frequency or higher average control delay with lower stops frequency at the Pareto front solution on the traffic model. The proposed algorithm performs the best with four other famous MOPSO on the traffic model in terms of the mean hypervolume in table 2, and the reference point is determined at table 1. We analyzed the average delay and stops between the current traffic signal phase and the traffic model. For the first intersection, the current traffic signalized phase drive to the average delay is 53.24, and the stops frequency is 0.8063 in the Baihuajin intersection. For the second intersection, the current traffic signalized phase lead to the average delay is 34.56, and the stops frequency is 0.7503 in the Longshan intersection. The effective green time of each intersection signalized phase is not optimized correctly for the actual intersection data. When the signalized effective green time phase is not selected from the Pareto-front solution, it may lead to overabundant average delay and excess stops frequency. The effective green time of each phase needs to be adjusted precisely based on the actual flow data to optimize a high average delay with lower stops frequency, or low average delay with higher stops frequency.
.
This study presents a modified multi-objective particle swarm optimization algorithm called MCMOPSO. It has two main contributions: multi-competition leader selection, and the effect on different inertia weights. Also, the external archive assigns the historical information to provide a good density of the found solutions. Multi- competition leader selection affects the flight trajectory for the particle swarm that can enhance convergence speed and produces well-distributed Pareto front solutions. We determine that the inertia weight can be set at 0.8 for having a good overall performance to strike a balance between exploration and exploitation in the CMOPSO equation. The new algorithm shows better performance results than other popular multi-objective algorithms in terms of inverted generational distance. Furthermore, the proposed algorithm was applied to a signalized traffic problem to optimize the average vehicle delay and stop frequency by considering the effective green time of each signalized phase.
.
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 |
