A Novel Hybrid Optimization Algorithm Based on GA and ACO for Solving Complex Problem

Bin Gao,Jing-Hua Zhu,Wen-chang Lang 보안공학연구지원센터 2015 International Journal of Multimedia and Ubiquitous Vol.10 No.8

In allusion to the deficiencies of the ant colony optimization algorithm for solving the complex problem, the genetic algorithm is introduced into the ant colony optimization algorithm in order to propose a novel hybrid optimization (NHGACO) algorithm in this paper. In the NHGACO algorithm, the genetic algorithm is used to update the global optimal solution and the ant colony optimization algorithm is used to dynamically balance the global search ability and local search ability in order to improve the convergence speed. Finally, some complex benchmark functions are selected to prove the validity of the proposed NHGACO algorithm. The experiment results show that the proposed NHGACO algorithm can obtain the global optimal solution and avoid the phenomena of the stagnation, and take on the fast convergence and the better robustness.

Simulated Annealing Optimization Bat Algorithm in Service Migration Joining the Gauss Perturbation

Zhao Guodong,Zhou Ying,Song Liya 보안공학연구지원센터 2015 International Journal of Hybrid Information Techno Vol.8 No.12

Bat algorithm is an optimization method inspired by the echo-location bats to search in nature, hunt prey behavior, combining multi-agent system and evolution mechanism. To improve the search results of BA algorithm, this paper proposes a gauss perturbation bats optimization algorithm based on simulated annealing (SAGBA). Firstly, the bionic principle, optimization mechanism and characteristics of the bat algorithm are analyzed and the algorithm optimization process are defined; Then the idea of the simulated annealing is put into bat optimization algorithm, and Gaussian disturbance is carried out to some individuals using the bat algorithm and strengthen the ability of the bat algorithm jumping out of local optimal solution. Finally, conduct simulations are respectively compared in 20 typical benchmark test functions among bat optimization algorithm, simulates annealing particle swarm algorithm and SAGBA algorithm. The results show that SAGBA algorithm not only increases the global convergence, but convergence speed and accuracy are better than other two algorithms.

위험물 수송 최적경로 탐색 알고리즘 개발: Efficient Vector Labeling 방법으로

박동주,정성봉,오정택 한국방재학회 2011 한국방재학회논문집 Vol.11 No.3

This paper deals with a methodology for searching optimal route of hazard material (hazmat) vehicles. When we make a decision of hazmat optimal paths, there is a conflict between the public aspect which wants to minimize risk and the private aspect which has a goal of minimizing travel time. This paper presents Efficient Vector Labeling algorithm as a methodology for searching optimal path of hazmat transportation, which is intrinsically one of the multi-criteria decision making problems. The output of the presented algorithm is a set of Pareto optimal paths considering both risk and travel time at a time. Also, the proposed algorithm is able to identify non-dominated paths which are significantly different from each other in terms of links used. The proposed Efficient Vector Labeling algorithm are applied to test bed network and compared with the existing k-shortest path algorithm. Analysis of result shows that the proposed algorithm is more efficient and advantageous in searching reasonable alternative routes than the existing one. 본 연구는 위험물 수송의 최적경로를 결정하는 방법론을 제안하였다. 위험물 차량의 최적경로를 결정할 때에는 위험도 최소화를 목적으로 하는 공공의 입장과 통행시간 최소화를 목적으로 하는 민간기업의 입장이 서로 상충한다. 본 연구에서는 이러한 다기준 의사결정(Multi-criteria decision making)문제 중 하나인 위험물 수송용 최적경로를 탐색하는 방법론으로 Efficient Vector Labeling(이하 EVL) 알고리즘을 제시하였다. EVL 알고리즘은 위험도와 통행시간을 동시에 고려하여 복수의 Pareto optimal 경로(또는 비지배경로)를 탐색하게 한다. 본 연구는 또한 탐색된 비지배경로간의 중복도를 제어할 수 있도록 설계하였다. 개발된 Efficient Vector Labeling 알고리즘을 Test bed network에 적용하여 기존의 경로탐색 방법론과 비교하였다. 적용결과 새로운 알고리즘이 기존의 알고리즘보다 합리적인 대안경로를 탐색할 수 있는 것으로 분석되었다.

할당 문제의 최적 알고리즘

이상운(Sang-Un Lee) 한국컴퓨터정보학회 2012 韓國컴퓨터情報學會論文誌 Vol.17 No.9

본 논문에서는 할당 문제의 최적해를 간단히 찾을 수 있는 알고리즘을 제안하였다. 일반적으로 할당 문제의 최적해는 Hungarian 알고리즘으로 구한다. 제안된 알고리즘은 Hungarian 알고리즘의 4단계 수행 과정을 1단계로 단축시켰으며, 행과 열의 최소 비용만을 선택하여 비용을 감소시키는 최적화 과정을 거쳐 최적해를 구하였다. 제안된 알고리즘을 27개의 균형 할당 문제와 7개의 불균형 할당 문제에 적용한 결과 유전자 알고리즘으로 찾지 못한 최적해를 찾는데 성공하였다. 제안된 알고리즘은 Hungarian 알고리즘의 수행 복잡도 O(n³)을 O(n)으로 향상시켰다. 따라서 제안된 알고리즘은 Hungarian 알고리즘을 대체하여 할당 문제에 일반적으로 적용할 수 있는 알고리즘으로 널리 활용될 수 있을 것이다. This paper suggests simple search algorithm for optimal solution in assignment problem. Generally, the optimal solution of assignment problem can be obtained by Hungarian algorithm. The proposed algorithm reduces the 4 steps of Hungarian algorithm to 1 step, and only selects the minimum cost of row and column then gets the optimal solution simply. For the 27 balanced and 7 unbalanced assignment problems, this algorithm finds the optimal solution but the genetic algorithm fails to find this values. This algorithm improves the time complexity O(n³) of Hungarian algorithm to O(n). Therefore, the proposed algorithm can be general algorithm for assignment problem replace Hungarian algorithm.

A Novel Hybrid Optimization Algorithm and its Application in Solving Complex Problem

Hao Jia 보안공학연구지원센터 2015 International Journal of Hybrid Information Techno Vol.8 No.2

Ant colony optimization (ACO) algorithm is a new heuristic algorithm which has been demonstrated a successful technology and applied to solving complex optimization problems. But the ACO exists the low solving precision and premature convergence problem, particle swarm optimization (PSO) algorithm is introduced to improve performance of the ACO algorithm. A novel hybrid optimization (HPSACO) algorithm based on combining collaborative strategy, particle swarm optimization and ant colony optimization is proposed for the traveling salesman problems in this paper. The HPSACO algorithm makes use of the exploration capability of the PSO algorithm and stochastic capability of the ACO algorithm. The main idea of the HPSACO algorithm uses the rapidity of the PSO algorithm to obtain a series of initializing optimal solutions for dynamically adjusting the initial pheromone distribution of the ACO algorithm. Then the parallel search ability of the he ACO algorithm are used to obtain the optimal solution of solving problem. Finally, various scale TSP are selected to verify the effectiveness and efficiency of the proposed HPSACO algorithm. The simulation results show that the proposed HPSACO algorithm takes on the better search precision, the faster convergence speed and avoids the stagnation phenomena.

A Novel Hybrid Evolution Optimization Algorithm and its Application

Bin Gao,Jing-Hua Zhu,Wen-Chang Lang 보안공학연구지원센터 2015 International Journal of Database Theory and Appli Vol.8 No.5

For the premature convergence and initial pheromone distribution problem of ant colony optimization algorithm, an improved particle swarm optimization (MPSO) algorithm is introduced into ant colony optimization algorithm in order to propose a novel hybrid evolution optimization (HEACO) algorithm in this paper. In the proposed HEACO algorithm, the ergodicity of the chaos is used to initialize the swarm in order to enhance the diversity of the particle swarm, and adjust the mutation probability and inertia weighting factor in order to improve the capability of local and global search. Then the MPSO algorithm is used to control the parameters of the heuristic factor, pheromone evaporation coefficient, and the stochastic selection threshold in order to effectively overcome the parameter influences of ACO, reduce the numbers of useless experiments and balance the developing optimal solution and enlarging search space. A series of typical traveling salesman problems are selected to validity the effectiveness of the proposed HEACO algorithm. The simulation results show that the performance of the proposed HEACO algorithm is better than the traditional ACO algorithm and PSO algorithm. So the proposed HEACO algorithm can effectively improve the solving efficiency and quality, and speed up the convergence and computation.

The Intelligent Task Scheduling Algorithm in Cloud Computing with Multistage Optimization

XiaoLi He,Yu Song,Ralf Volker Binsack 보안공학연구지원센터 2016 International Journal of Grid and Distributed Comp Vol.9 No.4

There’re huge numbers of users and various tasks need to be handled in the cloud computing environment, the high effective task scheduling algorithm is one of the crucial problems that the cloud computing need to solve. Aiming to the model structure of cloud computing, in this article it introduces the Particle Swarm Optimization algorithm (PSO) and Ant Colony Optimization algorithm (ACO) to combine with optimized task scheduling algorithm. First it takes the particle swarm optimization algorithm to generate the initial scheduling results, and introduces the random inertia weight to improve the scheduling ability of the algorithm, then to take the generated results of improved particle swarm optimization algorithm as the initial pheromones of the ant colony algorithm to find out the optimal scheduling scheme, and use the elitist strategy and crossover operator in the genetic algorithm to improve the ant colony algorithm, among the algorithms to use multistage optimization algorithm to improve the operating efficiency. The experimental results show that under the same conditions, the total task completion time of improved algorithm has been reduced and its performance advantage are getting more obvious with the increased task measures.

유전알고리즘 기반 최적화 건축설계 툴, 갈라파고스의 기능적 특성 연구

이우형 ( Lee Woohyoung ) 한국공간디자인학회 2020 한국공간디자인학회논문집 Vol.15 No.8

(연구배경 및 목적) 최근 다양한 디지털 설계지원 툴의 등장으로 건축설계에 있어 다양한 혁신의 기회를 제공하고 있다. 특히 파라메트릭 환경상의 알고리즘 기반 최적화 툴은 자의적 판단에 의존한 전통적 설계과정의 한계에 대한 과학적 객관성을 지원한다. 그러나 이러한 최적화 툴의 활용은 다음의 문제로 인해 그 실무적 활용성에 제한을 받는다. 첫째, 다양한 알고리즘 기반 최적화 툴이 존재하나 툴 간의 특징과 장단점에 대한 이해의 부족이다. 둘째, 도출된 솔루션에 대한 이해와 해석의 제한을 받는다. 이에 본 연구는 알고리즘 기반 최적화 툴 활용의 저변확대를 위해 상기 제한사항에 주목하여 현재 건축분야에서 활용도가 가장 높은 최적화 툴인 갈라파고스의 활용성과 성능평가를 수행하므로 최적화 툴의 이해와 해석을 도출하여 건축설계에 대한 잠재적 활용가능성을 확대하고자 한다. (연구방법) 본 논문은 라이노 그라스하퍼(Rhino Grasshopper)의 유전알고리즘(Genetic Algorithm) 기반 최적화 에드온(Add-On)인 갈라파고스(Galapagos)를 선정하고 그가 제공하는 두 연산기인 진화연산기(Evolutionary Solver)와 열처리연산기(Simulated Annealing Solver)를 활용하여 설정된 예제에 대한 최적화 과정을 시험하고 이를 통해 도출된 솔루션을 분석하므로 툴 간의 특성 및 활용성을 살펴본다. 이를 위해 본 논문은 다음과 같이 구성된다. 첫째, 건축설계와 최적화, 갈라파고스를 중심으로 다양한 최적화 툴들의 특징에 대한 이론적 고찰을 진행한다. 둘째, 선정된 두 연산기를 활용하여 설정된 예제에 대한 시나리오별 다양한 최적화 솔루션을 도출한다. 예제의 세부조건은 동일 면적의 볼륨에 대한 평면적 장단변비, 지붕 형태, 향에 대한 방위를 매개변수로 정의하고 외피에 대한 절기별 최적 일사량을 적합도로 설정한다. 셋째, 도출된 솔루션에 대한 적합도 수치의 수준 및 변화패턴 그리고 유전적 특징을 분석하고 이를 통해 두 연산기의 적합도 품질 및 다중목적에 대한 적합성에 관련된 결과를 도출한다. (결과) 이러한 과정을 거쳐 다음의 결론을 도출하였다 1)갈라파고스의 효율적 활용을 위해 두 연산기가 가진 검색 특징을 고려하여 양 연산기의 복합적 활용방식을 제안한다. 2)갈라파고스의 두 연산기는 건축설계가 가진 다중목적에 대한 각각의 한계를 노출하며 보다 정교한 최적화 결과를 위해 다중목적최적화에 특화된 에드온의 활용이 요구된다. 3)건축설계에 대한 최적화 툴의 적용성 확대를 위해 사용자 눈높이에 적합한 활용 매뉴얼의 개발이 요구된다. (결론) 이를 통해 최종적으로 각 연산기가 가진 최적화의 과정적 특징과 도출된 솔루션의 비교분석을 통해 두 연산기의 효율적 활용방안을 알아보는 동시에 현시점에서의 한계와 개선 방안을 도출한다. 이를 통해 궁극적으로 건축설계과정에 과학적 객관성에 기초한 종합적 설계조건의 통합적 최적화를 지원하는 새로운 설계방법의 가능성을 넓히고자 한다. (Background and Purpose) The recent emergence of various digital design tools has provided opportunities for various innovations in architectural design. In particular, the grafting of algorithm-based optimization tools in a parametric environment supports scientific objectivity to the limitations of the traditional design process that relies on arbitrary judgment. However, the use of this optimization tool is limited. First, there are various algorithm-based optimization tools, but there is a lack of understanding considering their use. Second, the understanding and interpretation of the derived solution are limited. Therefore, to expand the use of algorithm-based optimization tools, this study conducted applicability and performance evaluation of Galapagos, the most highly utilized optimization tool in the current architectural design. (Method) This study selected Galapagos, an optimization add-on based on a genetic algorithm in Rhino Grasshopper. The optimization process was tested using Galapagos’ two solvers: the Evolutionary Solver and the Simulated Annealing Solver. Moreover, the derived solution was analyzed to examine the characteristics and utility between solvers. To this end, the study is organized as follows. First, a theoretical review of the characteristics of various optimization tools was conducted, focusing on architectural design and optimization, and Galapagos. Second, using each selected solver, various optimization solutions were derived for each scenario in the example. In the detailed conditions of the example, the planar ratio with the same area, the shape of the roof, and the building orientation were defined as parameters, and the optimal solar radiation for each season was set as a fitness value. Third, we analyzed the level of fitness value, changing pattern, and genetic characteristics of the derived solution, and derived results related to the fitness quality of the two solvers and the application on multi-purpose problem. (Results) Through this process, we derived the following: (1) For efficient use of Galapagos, we propose a combined application method of both solvers; (2) the two solvers of Galapagos expose each limit to the multi-purpose of architectural design, and for more elaborate optimization results, the use of add-ons dedicated to multi-purpose optimization is required; (3) to expand the applicability of the optimization tool for architectural design, it is required to develop an application manual suitable for the user's level. (Conclusion) Finally, through the comparative analysis of the optimization process characteristics of each solver, we found the efficient utilization of them, simultaneously drawing the limitations and improvement at the present perspective. Subsequently, we intend to expand the possibilities of new design methods that ultimately support the integrated optimization of comprehensive design conditions based on scientific objectivity in the architectural design.

Optimal Location of FACTS Devices Using Adaptive Particle Swarm Optimization Hybrid with Simulated Annealing

Ali Ajami,Gh. Aghajani,M. Pourmahmood 대한전기학회 2010 Journal of Electrical Engineering & Technology Vol.5 No.2

This paper describes a new stochastic heuristic algorithm in engineering problem optimization especially in power system applications. An improved particle swarm optimization (PSO) called adaptive particle swarm optimization (APSO), mixed with simulated annealing (SA), is introduced and referred to as APSO-SA. This algorithm uses a novel PSO algorithm (APSO) to increase the convergence rate and incorporate the ability of SA to avoid being trapped in a local optimum. The APSO-SA algorithm efficiency is verified using some benchmark functions. This paper presents the application of APSO-SA to find the optimal location, type and size of flexible AC transmission system devices. Two types of FACTS devices, the thyristor controlled series capacitor (TCSC) and the static VAR compensator (SVC), are considered. The main objectives of the presented method are increasing the voltage stability index and over load factor, decreasing the cost of investment and total real power losses in the power system. In this regard, two cases are considered: single-type devices (same type of FACTS devices) and multi-type devices (combination of TCSC, SVC). Using the proposed method, the locations, type and sizes of FACTS devices are obtained to reach the optimal objective function. The APSO-SA is used to solve the above non?linear programming optimization problem for better accuracy and fast convergence and its results are compared with results of conventional PSO. The presented method expands the search space, improves performance and accelerates to the speed convergence, in comparison with the conventional PSO algorithm. The optimization results are compared with the standard PSO method. This comparison confirms the efficiency and validity of the proposed method. The proposed approach is examined and tested on IEEE 14 bus systems by MATLAB software. Numerical results demonstrate that the APSO-SA is fast and has a much lower computational cost.

Optimization of Location, Topology and Number of Bracing Spans in Steel Structures Using Multi Meta-Heuristic Based Search Method and Dynamic Constraints

Amirhosein Mohajer,Vahidreza Kalatjari,Mohammadhosein Talebpour 한국강구조학회 2022 International Journal of Steel Structures Vol.22 No.1

This study aims to optimize the weight of steel frames (as the objective function) to satisfy the legal constraints (inter-story drift and strength). The ultimate goal was to select an optimal arrangement and coordinate the two types of convergent bracing (multi-story X-bracing and X-bracing) in low, mid, and high-rise steel frames with specifi c dimensions and spans. In the end, an optimal weight design will be presented for the frames under the design constraints (by LRFD method), frequency, drift, and position of braces in frame height, and the amount of the tensile force of braces. Since the frequency constraints in design variables are highly nonlinear and non-convex, it is cumbersome to use them in optimization problems. In this research, the frames have been optimized using the connection between two software OPENSEES and MATLAB based on a multi meta-heuristic optimization algorithm with discrete variables (a new, mixed-method based on parallel island model with four islands). The fi ndings of this research include the optimal position of braces, sections, and convergence history for the frames under a multi meta-heuristic optimization algorithm. The diagrams of convergence history were also provided for the particle swarm algorithm in mid-rise frames. The results show the superiority of the multi meta-heuristic search algorithm in the convergence speed and the quality of the optimal response compared to the particle swarm optimization algorithm. Optimizing with the multi meta-heuristic algorithm reduces the impact of parameters and the relations governing the operation. Finally, the optimal design is obtained. According to the results, the multi-story X-bracing frames (the combination of inverted V-Bracing and V-Bracing) have more optimized weight and, thus, better structural response than the X-bracing frames. Placing braces in the middle spans of frames and adjacent to each other was the optimal design and position for all frames.