School of Science and Technology 科技學院
Computing Programmes 電腦學系

An Investigation of Multi-Objective Particle Swarm Optimization Algorithm for Better Performance and Its Application to Signalized Traffic Problem

Man Chung YUEN

ProgrammeBachelor of Computing with Honours in Internet Technology
SupervisorProf. Vanessa Ng
AreasAlgorithms
Year of Completion2020
AwardMerit of IEEE (HK) Computational Intelligence Chapter 17th FYP Competition

Objectives

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:

  • Study the problem of the multi-objective algorithm.
  • Improve the state-of-the-art MOPSO algorithm.
  • Compare the proposed algorithm with the existing algorithm.
  • Practice the proposed algorithm to the real-world problem.

Video Demonstration

Background and Methodology

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:

image: FileManager: file name not exists

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).

Evaluation

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.

.

Conclusion and Future Development

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 Chiu
Marketing Director
3DP Technology Limited

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.

Krutz Cheuk
Biomedical Engineer
Hong Kong Sanatorium & Hospital

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
Software and Hardware Engineer
Innovation Team Company Limited

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 CodeTitleCredits
 COMP S321FAdvanced Database and Data Warehousing5
 COMP S333FAdvanced Programming and AI Algorithms5
 COMP S351FSoftware Project Management5
 COMP S362FConcurrent and Network Programming5
 COMP S363FDistributed Systems and Parallel Computing5
 COMP S382FData Mining and Analytics5
 COMP S390FCreative Programming for Games5
 COMP S492FMachine Learning5
 ELEC S305FComputer Networking5
 ELEC S348FIOT Security5
 ELEC S371FDigital Forensics5
 ELEC S431FBlockchain Technologies5
 ELEC S425FComputer and Network Security5
 Course CodeTitleCredits
 ELEC S201FBasic Electronics5
 IT S290FHuman Computer Interaction & User Experience Design5
 STAT S251FStatistical Data Analysis5
 Course CodeTitleCredits
 COMPS333FAdvanced Programming and AI Algorithms5
 COMPS362FConcurrent and Network Programming5
 COMPS363FDistributed Systems and Parallel Computing5
 COMPS380FWeb Applications: Design and Development5
 COMPS381FServer-side Technologies and Cloud Computing5
 COMPS382FData Mining and Analytics5
 COMPS390FCreative Programming for Games5
 COMPS413FApplication Design and Development for Mobile Devices5
 COMPS492FMachine Learning5
 ELECS305FComputer Networking5
 ELECS363FAdvanced Computer Design5
 ELECS425FComputer and Network Security5