Resistance distance has been studied extensively in the past years, with the majority of previous studies devoted to undirected networks, in spite of the fact that various realistic networks are ...directed. Although several generalizations of resistance distance on directed graphs have been proposed, they either have no physical interpretation or are not a metric. In this paper, we first extend the definition of resistance distance to strongly connected directed graphs based on random walks and show that the two-node resistance distance on directed graphs is a metric. Then, we introduce the Laplacian matrix for directed graphs that subsumes the Laplacian matrix of undirected graphs as a particular case, and use its pseudoinverse to express the two-node resistance distance, and many other relevant quantities derived from resistance distances. Moreover, we define the resistance distance between a vertex and a vertex group on directed graphs and further define a problem of optimally selecting a group of fixed number of nodes, such that their resistance distance is minimized. Since this combinatorial optimization problem is NP-hard, we present a greedy algorithm with a proved approximation ratio, and conduct experiments on model and realistic networks to validate the performance of this approximation algorithm.
Bat algorithm is a population metaheuristic proposed in 2010 which is based on the echolocation or bio-sonar characteristics of microbats. Since its first implementation, the bat algorithm has been ...used in a wide range of fields. In this paper, we present a discrete version of the bat algorithm to solve the well-known symmetric and asymmetric Traveling Salesman Problems. In addition, we propose an improvement in the basic structure of the classic bat algorithm. To prove that our proposal is a promising approximation method, we have compared its performance in 37 instances with the results obtained by five different techniques: evolutionary simulated annealing, genetic algorithm, an island based distributed genetic algorithm, a discrete firefly algorithm and an imperialist competitive algorithm. In order to obtain fair and rigorous comparisons, we have conducted three different statistical tests along the paper: the Student׳s t-test, the Holm׳s test, and the Friedman test. We have also compared the convergence behavior shown by our proposal with the ones shown by the evolutionary simulated annealing, and the discrete firefly algorithm. The experimentation carried out in this study has shown that the presented improved bat algorithm outperforms significantly all the other alternatives in most of the cases.
Supply chain network design (SCND) models and methods have been the subject of several recent literature review surveys, but none of them explicitly includes sustainable development as a main ...characteristic of the problem considered. The aim of this review is to bridge this gap. The paper analyzes 87 papers in the field of supply chain network design, covering mathematical models that include economic factors as well as environmental and/or social dimensions. The review is organized along four research questions asking (i) which environmental and social objectives are included, (ii) how are they integrated into the models, (iii) which methods and tool are used and finally (iv) which industrial applications and contexts are covered in these models. The review finds that there are a number of limitations to the current research in sustainable SCND. The narrow scope of environmental and social measures in current models should go beyond limited greenhouse gas indicators to broader life-cycle approaches including new social metrics. The more effective inclusion of uncertainty and risk in models with improved multi-objective approaches is also needed. There are also significant gaps in the sectors used to test models limiting more general applicability. The paper concludes with promising new avenues of research to more effectively include sustainability into SCND models.
•We review 87 papers in the field of sustainable supply chain network design.•The papers reviewed address at least two dimensions of sustainable development.•We give a special focus on Life-Cycle Assessment (LCA) based models.•We review modeling, solution techniques and fields of application.
Nowadays, most of real world problems are complex and hence they cannot be solved by exact methods. So generally, we have to utilize approximate methods such as metaheuristics. So far, a significant ...amount of metaheuristic algorithms are proposed which are different with together in algorithm motivation and steps. Similarly, this paper presents the Tree Growth Algorithm (TGA) as a novel method with different approach to address optimization tasks. The proposed algorithm is inspired by trees competition for acquiring light and foods. Diversification and intensification phases and their tradeoff are detailed in the paper. Besides, the proposed algorithm is verified by using both mathematical and engineering benchmarks commonly used in this research area. This new approach in metaheuristic is compared and studied with well-known optimization algorithms and the comparison of TGA with standard versions of these employed algorithms showed the superiority of TGA in these problems. Also, convergence analysis and significance tests via some nonparametric technique are employed to confirm efficiency and robustness of the TGA. According to the results of conducted tests, the TGA can be considered as a successful metaheuristic and suitable for optimization problems. Therefore, the main purpose of providing this algorithm is achieving to better results, especially in continuous problems, due to the natural behavior inspired by trees.
•A novel metaheuristic algorithm called TGA inspired by trees behavior is developed.•A comprehensive literature review of metaheuristics have been proposed.•Taguchi method is utilized to tune the parameters of the algorithms.•TGA is evaluated using performance evaluation and statistical analysis.•TGA is measured by thirty benchmark functions and five engineering problems.
Cutting Stock Problems are the most studied NP-Hard combinatorial problems among optimization problems. An One-dimensional Cutting Stock Problem (1-CSP), which aims to create cutting patterns to ...minimize trim loss, is one of the best known optimization problems. The difficulty of the solution stages and the lack of a definite solution method that can be applied to all problems have caused these problems to attract a lot of attention by researchers. This study includes a hybrid solution algorithm combined with iterative trim loss algorithm and Monte Carlo simulations, and a comparative study of the method with the solution methods in the literature, for the solution of orders to be obtained with minimum cutting loss from the same type of stocks.
This paper provides an extensive review of the popular multi-objective optimization algorithm NSGA-II for selected combinatorial optimization problems viz. assignment problem, allocation problem, ...travelling salesman problem, vehicle routing problem, scheduling problem, and knapsack problem. It is identified that based on the manner in which NSGA-II has been implemented for solving the aforementioned group of problems, there can be three categories: Conventional NSGA-II, where the authors have implemented the basic version of NSGA-II, without making any changes in the operators; the second one is Modified NSGA-II, where the researchers have implemented NSGA-II after making some changes into it and finally, Hybrid NSGA-II variants, where the researchers have hybridized the conventional and modified NSGA-II with some other technique. The article analyses the modifications in NSGA-II and also discusses the various performance assessment techniques used by the researchers, i.e., test instances, performance metrics, statistical tests, case studies, benchmarking with other state-of-the-art algorithms. Additionally, the paper also provides a brief bibliometric analysis based on the work done in this study.
A multi-objective optimization problem can be solved by decomposing it into one or more single objective subproblems in some multi-objective metaheuristic algorithms. Each subproblem corresponds to ...one weighted aggregation function. For example, MOEA/D is an evolutionary multi-objective optimization (EMO) algorithm that attempts to optimize multiple subproblems simultaneously by evolving a population of solutions. However, the performance of MOEA/D highly depends on the initial setting and diversity of the weight vectors. In this paper, we present an improved version of MOEA/D, called EMOSA, which incorporates an advanced local search technique (simulated annealing) and adapts the search directions (weight vectors) corresponding to various subproblems. In EMOSA, the weight vector of each subproblem is adaptively modified at the lowest temperature in order to diversify the search toward the unexplored parts of the Pareto-optimal front. Our computational results show that EMOSA outperforms six other well established multi-objective metaheuristic algorithms on both the (constrained) multi-objective knapsack problem and the (unconstrained) multi-objective traveling salesman problem. Moreover, the effects of the main algorithmic components and parameter sensitivities on the search performance of EMOSA are experimentally investigated.
Celotno besedilo
Dostopno za:
DOBA, IZUM, KILJ, NUK, PILJ, PNG, SAZU, SIK, UILJ, UKNU, UL, UM, UPUK
Link scheduling in device-to-device (D2D) networks is usually formulated as a non-convex combinatorial problem, which is generally NP-hard and difficult to get the optimal solution. Traditional ...methods to solve this problem are mainly based on mathematical optimization techniques, where accurate channel state information (CSI), usually obtained through channel estimation and feedback, is needed. To overcome the high computational complexity of the traditional methods and eliminate the costly channel estimation stage, machine leaning (ML) has been introduced recently to address the wireless link scheduling problems. In this article, we propose a novel graph embedding based method for link scheduling in D2D networks. We first construct a fully-connected directed graph for the D2D network, where each D2D pair is a node while interference links among D2D pairs are the edges. Then we compute a low-dimensional feature vector for each node in the graph. The graph embedding process is based on the distances of both communication and interference links, therefore without requiring the accurate CSI. By utilizing a multi-layer classifier, a scheduling strategy can be learned in a supervised manner based on the graph embedding results for each node. We also propose an unsupervised manner to train the graph embedding based method to further reinforce the scalability and develop a K-nearest neighbor graph representation method to reduce the computational complexity. Extensive simulation demonstrates that the proposed method is near-optimal compared with the existing state-of-art methods but is with only hundreds of training network layouts. It is also competitive in terms of scalability and generalizability to more complicated scenarios.
The evolutionary algorithm has been extensively used to solve a range of combinatorial optimization problems. The adaptability of evolutionary algorithm mechanisms provides diverse approaches to ...handle combinatorial optimization challenges. This survey paper aims to comprehensively review the recent evolutionary algorithm variants in addressing combinatorial optimization problems. Research works published from the year 2018 to 2022 are identified in terms of problem representation and evolutionary strategies adopted. The mechanisms and strategies used in evolutionary algorithms to address different types of combinatorial optimization problems are discovered. Two main aspects are used to classify the evolutionary algorithm variants: population-based and evolutionary strategies (variation and replacement). It is observed that the hybrid evolutionary algorithm is mostly applied in addressing the problems. Hybridization in evolutionary algorithm mechanisms such as initialization methods, local searches, specific design operators, and self-adaptive parameters enhance the algorithm’s performance. Other metaheuristic approaches such as genetic algorithm, differential evolution algorithm, particle swarm optimization, and ant colony optimization are still preferable to address combinatorial optimization problems. Challenges and opportunities of evolutionary algorithms in combinatorial optimization problems are included for further exploration in the field of optimization research.
PDF
