School of Science and Technology 科技學院
Computing Programmes 電腦學系
| Programme | Bachelor of Science with Honours in Computing |
| Supervisor | Dr. Vanessa Ng |
| Areas | Artificial Intelligence and Intelligent Systems |
| Year of Completion | 2013 |
| Award | IEEE Computational Intelligence Chapter Hong Kong FYP Competition 2013 First Runner-Up |
The aim of this project is to enhance the searching ability of particle swarm optimization (PSO) in multi-objective problems and hence produce a better result. Besides maximizing the number of found solutions, selecting elitists among the found solutions is important. The elitists should both have a good distribution and high accuracy. The elitists must be store properly. Moreover, other algorithms are needed for comparison. Suitable metrics are necessary to indicate the performance of all the algorithms. Visualization is another important issue to show the performance of all the compared algorithms.
To achieve the aim, the main objective of the project is to make a new proposal for PSO in multi-objective optimization and verify it. The project has defined a number of sub-objectives as follows:
Particle Swarm Optimization (PSO) is an iterative process to find out solutions in artificial intelligence techniques. It was presented by James Kennedy and Russell C.Eberhartin 1995, inspired by the behavior of swarms. Like bird flocking, there are a number of birds moving in a given search-space and these birds find the location of food using its own experience and neighboring bird's experience. To simulate bird flocking, first, a group of particles (birds) are randomly initialized over a search space. Then each particle's velocity is initialized. The whole swarm then starts its motion. In every cycle, the velocity of each particle is updated according to its previous best position and the best position found by any particle in the swarm. So each particle will move to a new position using the updated velocity. The details to stimulate a searching swarm is shown below:
Non-dominated Sorting Genetic Algorithm II (NSGA-II)
Evolutionary algorithms have been developed to solve multi-objective optimization problems for years (PAES, microGA, NSGA and so on). At first, a random parent population is created. The population is then sorted and evaluation is performed. Then a child population is created by using binary tournament selection, recombination and mutation. After this generation (first generation), the procedure is different. Parent and child population are combined and then sorted. The new parent population is filled using the crowded comparison operator. Then the procedure goes back to the selection, crossover and mutation stage. The crowded comparison operator used is to preserve solutions' diversity, and the fast non-dominated sorting approach to identify a list of the non-dominated front. The NGSA-II main algorithm is shown below:
Multi-objective particle swarm optimization (MOPSO)
Computer scientists have started to extend PSO to deal with multi-objective problems after the first release of PSO. The position and velocity of the population are initialized. Evaluation is carried out to calculate the fitness value of each particle. The non-dominated particles are chosen and stored into the archive. After that, update the past best position of each particle. Then generate hypercubes of the search space to locate the particles. Apply roulette-wheel selection to choose the global best particle and update population's velocity and position. Then the process goes back to the evaluation stage until the maximum number of generations has been reached. The MOPSO main algorithm is as follows:
Use of Crowding Distance in Multi-objective Particle Swarm Optimization (MOPSO-CD)
Crowding distance computation is used to select global best and delete non-dominated solutions when the archive is full. Mutation operator is used to enrich the searching ability of the proposed algorithm. First, the position and velocity of the population are initialized. Then the past best position of each particle in the swarm is found. Evaluation is carried out to calculate the fitness value of each particle. The non-dominated particles are chosen and stored into the archive (update archive). After that, crowding distance values of the archive members are calculated and the values are sorted in descending order. So that a global best leader can be selected from particles of a specified top portion (i.e. 10%). After updating the population's velocity and position, the process goes back to the find past best stage until the maximum number of generations has been reached. The MOPSO-CD algorithm is as follows:
Our proposed algorithm is called MOPSO-SR. Three main measures are adapted: the use of an external archive to store the non-dominated solutions, mechanism of selecting leaders to group and guide the swarm using square root computation and delete non-dominated solutions using square root computation when the archive is full.
Under our proposed guiding mechanism, particles seems are guided to the nearest archive member. This is true in general. However, in some conditions, particles are not only guided to the nearest archive member. Such mechanism avoids particles converge to a single global/local minimum/maximum and maintains divergence of found solutions. The left draft shows below that Particle C does not choose the nearest archive member B as leader. Instead, it chooses archive member A as leader. So, Particle C moves towards A at first. After one generation, square root value of C to each archive member is re-calculated again and Particle C selects B as leader but not A.
The duty of the archive is to store the found solutions. Archive controller is an important mechanism to select appropriate solutions. We adopt an archive controller similar to the archive controller of MOPSO. However, we implement the deletion mechanism using square root computation, such mechanism is responsible to maintain a fixed-size archive and a well-spread found Pareto front, making the archive controller unique.
This part introduces the insertion mechanism of the archive controller. For each found solution, it needs to be compared with all the non-dominated solutions stored in archive one by one. When the archive is empty, the found solution will be inserted into the archive. If the new solution dominates the old solution, the old solution will be replaced by the new solution. If the new solution is dominated by the old solution, the new solution will not be added into the archive. If the new solution is not comparable to the old solutions, the new solution will be added. Note that for each new found solution, it needs to be compared with every stored solution in the archive one by one until the last stored solution, or the new solution is dominated by one of the old solutions.
The three main measures mentioned above are included in the proposed algorithm, making the algorithm is capable of solving multi-objective problems. At the beginning, the position, speed and past best of the searching particles are initialized. Then evaluate each particle base on objective functions (fitness functions) which we would like to minimize/maximize. The calculated fitness values of particles are compared with one another, the one that is not dominated (non-dominated solution) by others will be added into the archive. The following actions will repeat until the end of iteration. For each particle, calculate its square root value with respect to each archive member and selects its leader based on the lowest square root value. Then each particle performs its flight (update its velocity and new position). After moving to the new position, evaluation is carried out to calculate the fitness value of each particle. After that, update the archive and the past best position of the swarm. If the archive is full, square root calculation is invoked to remove the most crowded member, and new member is then be inserted. The archive content keeps updating until the end of the searching process.
To verify the searching ability of our proposed MOPSO-SR, five test cases were taken and four metrics were adopted. We compared our proposed algorithm MOPSO-SR, with other three algorithms. They are NSGA-II, MOPSO and MOPSO-CD. For each test case with each algorithm, 20 independent runs were carried out. For each run, 100 generations with 100 population size were adopted. All the runs were performed under the same environment (Matlab) on Intel(R) Core(TM) i3 CPU M350 @ 2.27GHz with 4GB RAM. To show the performance of each algorithm, four different metrics were used. For easier to introduce the four metrics, the following is introduced:
| Generations | 20 | 50 | 100 | 150 | 200 |
|---|---|---|---|---|---|
| Spacing | |||||
| Average | 0.440361 | 0.029911 | 0.017611 | 0.017324 | 0.016511 |
| Median | 0.409784 | 0.029319 | 0.017315 | 0.01717 | 0.016652 |
| Std. Dev. | 0.177001 | 0.0048 | 0.001347 | 0.001889 | 0.001585 |
| Error ratio | |||||
| Average | 0.108785 | 0.069 | 0.0525 | 0.058 | 0.0485 |
| Median | 0.113248 | 0.07 | 0.05 | 0.055 | 0.05 |
| Std. Dev. | 0.056788 | 0.022455 | 0.023141 | 0.024409 | 0.015985 |
| Generational distance | |||||
| Average | 0.013928 | 0.000141 | 4.42E-05 | 4.48E-05 | 3.22E-05 |
| Median | 0.008319 | 4.92E-05 | 1.83E-05 | 2.09E-05 | 2.17E-05 |
| Std. Dev. | 0.015015 | 0.000215 | 5.75E-05 | 5.26E-05 | 2.72E-05 |
| Time (seconds) | |||||
| Average | 0.295547 | 1.613008 | 4.851279 | 9.439615 | 13.86244 |
| Median | 0.299553 | 1.621406 | 4.923882 | 9.446625 | 13.87568 |
| Std. Dev. | 0.028447 | 0.187779 | 0.239441 | 0.627475 | 0.81029 |
| Generations | 20 | 50 | 100 | 150 | 200 |
|---|---|---|---|---|---|
| Spacing | |||||
| Average | 0.304023 | 0.143583 | 0.127915 | 0.11952 | 0.121152 |
| Median | 0.270572 | 0.144123 | 0.126606 | 0.120925 | 0.120925 |
| Std. Dev. | 0.139115 | 0.017552 | 0.009033 | 0.008975 | 0.006447 |
| Error ratio | |||||
| Average | 0.580549 | 0.209 | 0.105 | 0.085 | 0.0625 |
| Median | 0.57375 | 0.2 | 0.11 | 0.09 | 0.065 |
| Std. Dev. | 0.100186 | 0.068664 | 0.035467 | 0.02911 | 0.02989 |
| Generational distance | |||||
| Average | 0.014773 | 0.004503 | 0.003069 | 0.002585 | 0.002256 |
| Median | 0.013772 | 0.004351 | 0.00331 | 0.002485 | 0.002201 |
| Std. Dev. | 0.005278 | 0.001179 | 0.000863 | 0.000659 | 0.000888 |
| Time (seconds) | |||||
| Average | 0.655563 | 2.914654 | 5.907873 | 10.88786 | 14.83046 |
| Median | 0.646982 | 2.953645 | 6.038845 | 10.822 | 14.56374 |
| Std. Dev. | 0.131278 | 0.541178 | 0.758784 | 1.326015 | 1.326434 |
| Generations | 20 | 50 | 100 | 150 | 200 |
|---|---|---|---|---|---|
| Spacing | |||||
| Average | 0.018406 | 0.010097 | 0.005806 | 0.004376 | 0.004136 |
| Median | 0.01835 | 0.008213 | 0.005605 | 0.004165 | 0.00391 |
| Std. Dev. | 0.003517 | 0.004212 | 0.001576 | 0.000957 | 0.000736 |
| Error ratio | |||||
| Average | 0.018 | 0.0205 | 0.0195 | 0.0195 | 0.0205 |
| Median | 0.02 | 0.02 | 0.015 | 0.02 | 0.02 |
| Std. Dev. | 0.013992 | 0.012344 | 0.015035 | 0.01191 | 0.013563 |
| Generational distance | |||||
| Average | 1.07E-05 | 1.4E-05 | 1.39E-05 | 1.25E-05 | 1.77E-05 |
| Median | 1.07E-05 | 1.07E-05 | 1.11E-05 | 1.11E-05 | 1.41E-05 |
| Std. Dev. | 1.98E-06 | 1.03E-05 | 7.77E-06 | 4.91E-06 | 1.1E-05 |
| Time (seconds) | |||||
| Average | 0.282421 | 1.965581 | 5.144581 | 12.76637 | 19.68625 |
| Median | 0.250141 | 1.896369 | 4.874001 | 12.22267 | 20.57937 |
| Std. Dev. | 0.171297 | 1.303524 | 1.755615 | 3.460555 | 6.583812 |
| Generations | 20 | 50 | 100 | 150 | 200 |
|---|---|---|---|---|---|
| Spacing | |||||
| Average | 0.015795 | 0.013477 | 0.007809 | 0.011371 | 0.010449 |
| Median | 0.016134 | 0.012721 | 0.007823 | 0.00999 | 0.009697 |
| Std. Dev. | 0.002694 | 0.002799 | 0.000458 | 0.004405 | 0.003788 |
| Error ratio | |||||
| Average | 0.0775 | 0.076 | 0.075 | 0.071 | 0.0605 |
| Median | 0.07 | 0.07 | 0.075 | 0.07 | 0.06 |
| Std. Dev. | 0.032907 | 0.021374 | 0.025649 | 0.030418 | 0.021879 |
| Generational distance | |||||
| Average | 2.07E-06 | 2.12E-06 | 2.01E-06 | 1.98E-06 | 2.09E-06 |
| Median | 2.05E-06 | 2.09E-06 | 2.07E-06 | 1.96E-06 | 2.11E-06 |
| Std. Dev. | 2.41E-07 | 2.42E-07 | 1.85E-07 | 2.41E-07 | 2.56E-07 |
| Time (seconds) | |||||
| Average | 0.357576 | 0.589878 | 0.873936 | 1.184632 | 1.383112 |
| Median | 0.362714 | 0.545489 | 0.798321 | 1.127677 | 1.217472 |
| Std. Dev. | 0.085925 | 0.156202 | 0.284892 | 0.396754 | 0.473868 |
| Generations | 20 | 50 | 100 | 150 | 200 |
|---|---|---|---|---|---|
| Spacing | |||||
| Average | 0.038646 | 0.0289 | 0.026898 | 0.02648 | 0.026165 |
| Median | 0.037796 | 0.028593 | 0.026759 | 0.02651 | 0.026171 |
| Std. Dev. | 0.004665 | 0.001466 | 0.000693 | 0.000332 | 0.000264 |
| Error ratio | |||||
| Average | 0.0095 | 0.003 | 0.003 | 0.0045 | 0.0035 |
| Median | 0.01 | 0 | 0 | 0 | 0 |
| Std. Dev. | 0.009445 | 0.004702 | 0.004702 | 0.006863 | 0.005871 |
| Generational distance | |||||
| Average | 2.6E-05 | 7.58E-06 | 5.78E-06 | 6.52E-06 | 6.34E-06 |
| Median | 1.02E-05 | 7.18E-06 | 5.6E-06 | 6.3E-06 | 6.16E-06 |
| Std. Dev. | 3.84E-05 | 2.41E-06 | 7.85E-07 | 1.79E-06 | 1.33E-06 |
| Time (seconds) | |||||
| Average | 0.695629 | 2.009974 | 3.640274 | 4.957879 | 6.288128 |
| Median | 0.685158 | 1.975672 | 3.608439 | 5.034816 | 6.332293 |
| Std. Dev. | 0.194544 | 0.273213 | 0.320454 | 0.465918 | 0.487584 |
This paper has presented a proposal for PSO to handle multi-objective problems. The searching ability of our proposed algorithm, MOPSO-SR has a strong searching ability and it is satisfying. The proposed approach can be regarded as an alternative method to solve multi-objective problems. Besides maximizing the number of found solutions, archive controller has been successfully implemented and it can select non-dominated solutions among the found solutions. It works well to store the elitists. When the archive is full, the archive can remove the unwanted non-dominated solutions and insert new solutions, using square root computation. Results show that such method can maintain good distribution of the found Pareto front. We have also implemented a mutation operator to enhance searching ability of our proposed algorithm. In addition, 5 test cases have been set up successfully, so that they can be used to verify the proposed algorithm. And comparison can be made with other three algorithms (NGSA-II, MOPSO and MOPSO-CD) using the test cases. Actually, MOPSO-SR performed better in most of the test cases. Visualization has been made and the searching process of each algorithm can be displayed. So others can know how the algorithms work.
Since this project focuses on solving 2 objective problems, the 3 or more objective problems have not been considered yet. We don't know if our proposed algorithm can handle those problems. Moreover, the parameters of the algorithm, c1(local weight), c2(global weight) and w(inertia weight), need to be finely tuned. So that the performance of the proposed algorithm can be maximize. This requires deeper knowledge in the algorithm.
The future work will focus on solving 3 or more objective problems. Also, a new method should be developed to avoid users spending too much time on tuning the parameters before the use of algorithm. We would like to focus more on the mutation operator because the mutation rate affects the result.
Copyright Leung Man Fai and Vanessa Ng 2013
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 |
