Browsing by Author "Oz, Dindar"

Now showing 1 - 7 of 7

Citation - WoS: 21
Citation - Scopus: 23
An improvement on the Migrating Birds Optimization with a problem-specific neighboring function for the multi-objective task allocation problem
(Elsevier Ltd, 2017) Dindar Öz; Oz, Dindar
Allocating tasks to processors is a well-known NP-Hard problem in distributed computing systems. Due to the lack of practicable exact solutions it has been attracted by the researchers working on heuristic-based suboptimal search algorithms. With the recent inclusion of multiple objectives such as minimizing the cost maximizing the throughput and maximizing the reliability the problem gets even more complex and an efficient approximate method becomes more valuable. In this work I propose a new solution for the multi-objective task allocation problem. My solution consists in designing a problem-specific neighboring function for an existing metaheuristic algorithm that is proven to be successful in quadratic assignment problems. The neighboring function namely greedy reassignment with maximum release (GR-MR) provides a dynamic mechanism to switch the preference of the search between the exploration and exploitation. The experiments validate both that the quality of the solutions are close to the optimal and the proposed method performs significantly better comparing to three other metaheuristic algorithms. Neighboring functions being the common reusable components of metaheuristic algorithms GR-MR can also be utilized by other metaheuristic-based solutions in the future. © 2017 Elsevier B.V. All rights reserved.
Citation - WoS: 4
Citation - Scopus: 3
An optimal algorithm for the obstacle neutralization problem
(American Institute of Mathematical Sciences PO Box 2604 Springfield MO 65801-2604, 2017) Ali Fuat Alkaya; Dindar Öz; Alkaya, Ali Fuat; Oz, Dindar
In this study an optimal algorithm is presented for the obstacle neutralization problem (ONP). ONP is a recently introduced path planning problem wherein an agent needs to swiftly navigate from a source to a destination through an arrangement of obstacles in the plane. The agent has a limited neutralization capability in the sense that the agent can safely pass through an obstacle upon neutralization at a cost added to the traversal length. The goal of an agent is to find the sequence of obstacles to be neutralized en route minimizing the overall traversal length subject to the neutralization limit. Our optimal algorithm consists of two phases. In the first phase an upper bound of the problem is obtained using a suboptimal algorithm. In the second phase starting from the bound obtained from phase I a k-th shortest path algorithm is exploited to find the optimal solution. The performance of the algorithm is presented with computational experiments conducted both on real and synthetic naval minefield data. Results are promising in the sense that the proposed method can be applied in online applications. © 2017 Elsevier B.V. All rights reserved.
Ant Colony Optimization for the Sensor Deployment Problem
(Institute of Electrical and Electronics Engineers Inc., 2023) Oz, Dindar
Citation - WoS: 13
Citation - Scopus: 3
Metaheuristic Algorithms for the Quadratic Assignment Problem
(IEEE, 2013) M. Fatih Tasgetiren; Quan-Ke Pan; P. N. Suganthan; Ikbal Ece Dizbay; Tasgetiren, M. Fatih; Suganthan, P. N.; Oz, Dindar; Pan, Quan-Ke; Dizbay, Ikbal Ece; Türkkahraman, Şeyda Melis
This paper presents two meta-heuristic algorithms to solve the quadratic assignment problem. The iterated greedy algorithm has two main components hich are destruction and construction procedures. The algorithm starts from an initial solution and then iterates through a main loop where first a partial candidate solution is obtained by removing a number of solution components from a complete candidate solution. Then a complete solution is reconstructed by inserting the partial solution components in the destructed solution. These simple steps are iterated until some predetermined termination criterion is met. We also present our previous discrete differential evolution algorithm modified for the quadratic assignment problem. The quadratic assignment problem is a classical NP-hard problem and its applications in real life are still considered challenging. The proposed algorithms were evaluated on quadratic assignment problem instances arising from real life problems as well as on a number of benchmark instances from the QAPLIB. The computational results show that the proposed algorithms are superior to the migrating birds optimization algorithm which appeared very recently in the literature. Ultimately 7 out of 8 printed circuit boards (PCB) instances are further improved.
Citation - Scopus: 1
Optimizing Wireless Sensor Network Deployment with Hybrid Genetic Algorithm
(Institute of Electrical and Electronics Engineers Inc., 2023) Dogukan Teber; Efekan Zafer Engin; Dindar Öz; Engin, Efekan Zafer; Teber, Dogukan; Oz, Dindar
Wireless Sensor Networks (WSNs) have vital applications in diverse domains including military environmental monitoring disaster management and security systems. Achieving both m-connectivity and k-coverage is critical for ensuring network reliability and effective area monitoring. In this study we propose a Hybrid Genetic Algorithm for Wireless Sensor Network deployment (HGA-WSN) that combines genetic algorithms with problem-specific local search to efficiently explore solutions. The paper compares HGA-WSN against a standard genetic algorithm a greedy heuristic and a standard simulated annealing implementation. The experiments encompass various problem instances considering different $\mathrm{m}\mathrm{k}$ and target count values. The results validate HGA-WSN's superior performance in terms of sensor count reduction. The algorithm's efficacy in optimizing WSN deployment across diverse applications is evident from its rapid convergence and enhanced connectivity and coverage achievements. © 2023 Elsevier B.V. All rights reserved.
Citation - WoS: 9
Citation - Scopus: 9
Scalable parallel implementation of migrating birds optimization for the multi-objective task allocation problem
(SPRINGER, 2021) Dindar Oz; Isil Oz; Oz, Isil; Oz, Dindar
As the distributed computing systems have been widely used in many research and industrial areas the problem of allocating tasks to available processors in the system efficiently has been an important concern. Since the problem is proven to be NP-hard heuristic-based optimization techniques have been proposed to solve the task allocation problem. Particularly the current cloud-based systems have been grown massively requiring multiple features like lower cost higher reliability and higher throughput, therefore the problem has become more challenging and approximate methods have gained more importance. Migrating birds optimization (MBO) algorithm offers successful solutions especially for quadratic assignment problems. Inspired by the movement of the birds it exhibits good results by its population-based approach . Since the algorithm needs to deal with many individuals in the population and the neighbor solution generation phase takes substantial time for large problem instances we need parallelism to have execution time improvements and make the algorithm practical for large-scale problems. In this work we propose a scalable parallel implementation of the MBO algorithm PMBO for the multi-objective task allocation problem. We redesigned the implementation of the MBO algorithm so that its computationally heavy independent tasks are executed concurrently in separate threads. We compare our implementation with three parallel island-based approaches. The experimental results demonstrate that our implementation exhibits substantial solution quality improvements for difficult problem instances as the computing resources namely parallelism increase. Our scalability analysis also presents that higher parallelism levels offer larger solution improvement for the PMBO over the island-based parallel implementations on very hard problem instances.
Citation - WoS: 1
Citation - Scopus: 1
SCATTER SEARCH WITH STOCHASTIC BEAM SEARCH ON THE COALITION FORMATION PROBLEM
(AMER INST MATHEMATICAL SCIENCES-AIMS, 2024) Dindar Oz; Tolga Bugra Altuntas; Altuntas, Tolga Bugra; Oz, Dindar
The coalition formation problem (CFP) is a crucial component of multi-agent systems (MAS) taking place in various areas in the real world with different variants. This study proposes a parallel metaheuristic algorithm for CFP. Our hybrid method combines two metaheuristic algorithms: the Scatter Search and the Beam Search. While the former ensures that the algorithm thor-oughly explores the search space the latter exploits the visited regions. We re-design Scatter Search's original implementation to perform the time-consuming independent areas of the task in parallel. We employ a perturbation mechanism inside the Beam Search that performs a big jump in the search space when it cannot find any improvement. Moreover we design a problem-specific repre-sentation that stores meta-information to save significant computational time. The proposed method is examined in parallel and sequential configurations and compared with an exact solver recent metaheuristic algorithms and the standard implementation of the Scatter Search. The experimental results show that our solution achieves considerable improvements in both configurations.