시뮬레이션 최적화 문제 해결을 위한 이산 입자 군집 최적화에서 샘플수와 개체수의 효과
The Effect of Sample and Particle Sizes in Discrete Particle Swarm Optimization for Simulation-based Optimization Problems
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
This paper deals with solution methods for discrete and multi-valued optimization problems. The objective function of the problem incorporates noise effects generated in case that fitness evaluation is accomplished by computer based experiments such as Monte Carlo simulation or discrete event simulation. Meta heuristics including Genetic Algorithm (GA) and Discrete Particle Swarm Optimization (DPSO) can be used to solve these simulation based multi-valued optimization problems. In applying these population based meta heuristics to simulation based optimization problem, samples size to estimate the expected fitness value of a solution and population (particle) size in a generation (step) should be carefully determined to obtain reliable solutions. Under realistic environment with restriction on available computation time, there exists trade-off between these values. In this paper, the effects of sample and population sizes are analyzed under well-known multi-modal and multi-dimensional test functions with randomly generated noise effects. From the experimental results, it is shown that the performance of DPSO is superior to that of GA. While appropriate determination of population sizes is more important than sample size in GA, appropriate determination of sample size is more important than particle size in DPSO. Especially in DPSO, the solution quality under increasing sample sizes with steps is inferior to constant or decreasing sample sizes with steps. Furthermore, the performance of DPSO is improved when OCBA (Optimal Computing Budget Allocation) is incorporated in selecting the best particle in each step. In applying OCBA in DPSO, smaller value of incremental sample size is preferred to obtain better solutions.
Abstract
This paper deals with solution methods for discrete and multi-valued optimization problems. The objective function of the problem incorporates noise effects generated in case that fitness evaluation is accomplished by computer based experiments such as Monte Carlo simulation or discrete event simulation. Meta heuristics including Genetic Algorithm (GA) and Discrete Particle Swarm Optimization (DPSO) can be used to solve these simulation based multi-valued optimization problems. In applying these population based meta heuristics to simulation based optimization problem, samples size to estimate the expected fitness value of a solution and population (particle) size in a generation (step) should be carefully determined to obtain reliable solutions. Under realistic environment with restriction on available computation time, there exists trade-off between these values. In this paper, the effects of sample and population sizes are analyzed under well-known multi-modal and multi-dimensional test functions with randomly generated noise effects. From the experimental results, it is shown that the performance of DPSO is superior to that of GA. While appropriate determination of population sizes is more important than sample size in GA, appropriate determination of sample size is more important than particle size in DPSO. Especially in DPSO, the solution quality under increasing sample sizes with steps is inferior to constant or decreasing sample sizes with steps. Furthermore, the performance of DPSO is improved when OCBA (Optimal Computing Budget Allocation) is incorporated in selecting the best particle in each step. In applying OCBA in DPSO, smaller value of incremental sample size is preferred to obtain better solutions.
참고문헌 (20)
- Aizawa, A.N., "Dynamic Control of Genetic Algorithms in a Noisy Environment", Proceeding of the Fifth International Conference on Genetic Algorithms, pp.103~115 (1993)
- Bartz-Beielstein, T, "Particle Swarm Optimization and Sequential Sampling in Noisy Environments", Proceedings of the 6th Metaheuristics International Conference (MIC2005), pp.89~94 (2005)
- Branke, J., "Genetic and Evolutionary Computation", pp.243~250 (2001), Morgan Kaufman
- Chen, C.-H., "Simulation Budget Allocation for Further Enhancing the Efficiency of Ordinal Optimization", Discrete Event Dynamic Systems : Theory and Applications, 10(3), pp.251~270 (2000)
- Fitzpatrick, J.M., "Genetic Algorithm in Noisy Environments", Machine Learning, 3(2), pp.101~120 (1988)
- Horng, S.-C., "Applying PSO and OCBA to minimize the Overkills and Re-Probes in Wafer Probe Testing", IEEE Transactions on Semiconductor Manufacturing, 25(3), pp.531~540 (2012)
- Jin, Y., "Evolutionary Optimization in Uncertain Environments-A Survey", IEEE Transactions on Evolutionary Computation, 9(3), pp.303~317 (2005)
- Kennedy, J., "A Discrete Binary Version of the Particle Swarm Algorithm", IEEE International Conference on Systems, Man, and Cybernetics, pp.4104~4108 (1997)
- Miller, B.L., "Genetic Algorithms, Selection Schemes and the Varying Effects of Noise", Evolutionary Computation, 4(2), pp.113~131 (1996)
- Pan, H., "Particle Swarm Optimization for Function Optimization in Noisy Environment", Applied mathematics and Computation, 181(2), pp.908~919 (2006)
- Pugh, J., "Discrete Multi-Valued Particle Swarm Optimization", Proceedings of IEEE Swarm Intelligence Symposium, pp.103~110 (2006)
- Rada-Juan, R.-V., "Optimal Computing Budget Allocation in Particle Swarm Optimization", GECCO ’13, pp.81~88 (2013)
- 송화창, "Photovoltaic System Allocation Using Discrete Particle Swarm Optimization with Multi-level Quantization", Journal of Electrical Engineering & Technology, 4(2), pp.185~193 (2009), 대한전기학회
- Veeramachaneni, K., "Probabilistically Driven Particle Swarms for optimization of Multi Valued Discrete Problems : Design and Analysis", Proceedings of IEEE Swarm Intelligence Symposium, pp.141~149 (2007)
- Vesterstrom, J., "A Comparative Study of Differential Evolution, Particle Swarm Optimization, and Evolutionary Algorithms on Numerical Benchmark Problems", Evolutionary Computation CEC 2004 Congress, 2, pp.1980~1987 (2004)
- Yang, X.-S., "Engineering Optimization : An Introduction with Metaheuristic Applications" (2010), John Wiley & Sons
- 임동순, "다수의 값을 갖는 이산적 문제에 적용되는 Particle Swarm Optimization", 산업경영시스템학회지, 36(3), pp.63~70 (2013), 한국산업경영시스템학회[DOI]
- Zhai, W., "Genetic Algorithms with Noisy Fitness", Mathematical and Computer Modeling, 23(11, pp.12) (1996), 131~142
- Zhang, R., "A Two stage hybrid particle swarm optimization algorithm for the stochastic job shop scheduling problem", Knowledge-Based Systems, 27, pp.393~406 (2012)
- Zhang, S., "Simulation Optimization Using the Particle Swarm Optimization with Optimal Computing Budget Allocation", Proceedings of the 2011 Winter Simulation Conference, pp.4303~4313 (2011)