Search

Meta-heuristic algorithms, especially evolutionary algorithms, have been frequently used to find near optimal solutions to combinatorial optimization problems. The evaluation of such algorithms is often conducted through comparisons with other algorithms on a set of benchmark problems. However, even if one algorithm is the best among all those compared, it still has difficulties in determining the true quality of the solutions found because the true optima are unknown, especially in dynamic environments. It would be desirable to evaluate algorithms not only relatively through comparisons with others, but also in absolute terms by estimating their quality compared to the true global optima. Unfortunately, true global optima are normally unknown or hard to find since the problems being addressed are NP-hard. In this paper, instead of using true global optima, lower bounds are derived to carry out an objective evaluation of the solution quality. In particular, the first approach capable of deriving a lower bound for dynamic capacitated arc routing problem (DCARP) instances is proposed, and two optimization algorithms for DCARP are evaluated based on such a lower bound approach. An effective graph pruning strategy is introduced to reduce the time complexity of our proposed approach. Our experiments demonstrate that our approach provides tight lower bounds for small DCARP instances. Two optimization algorithms are evaluated on a set of DCARP instances through the derived lower bounds in our experimental studies, and the results reveal that the algorithms still have room for improvement for large complex instances. [ABSTRACT FROM AUTHOR]

Traditional solvers for tackling combinatorial optimization (CO) problems are usually designed by human experts. Recently, there has been a surge of interest in utilizing deep learning, especially deep reinforcement learning, to automatically learn effective solvers for CO. The resultant new paradigm is termed neural combinatorial optimization (NCO). However, the advantages and disadvantages of NCO relative to other approaches have not been empirically or theoretically well studied. This work presents a comprehensive comparative study of NCO solvers and alternative solvers. Specifically, taking the traveling salesman problem as the testbed problem, the performance of the solvers is assessed in five aspects, i.e., effectiveness, efficiency, stability, scalability, and generalization ability. Our results show that the solvers learned by NCO approaches, in general, still fall short of traditional solvers in nearly all these aspects. A potential benefit of NCO solvers would be their superior time and energy efficiency for small-size problem instances when sufficient training instances are available. Hopefully, this work would help with a better understanding of the strengths and weaknesses of NCO and provide a comprehensive evaluation protocol for further benchmarking NCO approaches in comparison to other approaches. [ABSTRACT FROM AUTHOR]

Cooperative co-evolution (CC) is an evolutionary algorithm that adopts the divide-and-conquer strategy to solve large-scale optimization problems. It is difficult for CC to specify a suitable subpopulation size to solve different subproblems. The population diversity may be insufficient to search for the global optimum during subpopulations' evolution. In this paper, an adaptive method for enhancing population diversity is embedded in a contribution-based CC. In CC, there are two kinds of subpopulation: the convergent or stagnant subpopulations and the non-convergent and non-stagnant subpopulations. A method is proposed in the paper to evaluate the convergent and stagnant subpopulations' contributions to improving the best overall objective value, which is different from the contribution evaluation on the non-convergent and non-stagnant subpopulations. In each co-evolutionary cycle, the new CC adaptively determines to select a subpopulation, which can make a greater contribution to improving the best overall objective value, between the above two kinds of subpopulation to undergo evolution. When a convergent or stagnant subpopulation is selected to undergo evolution, the subpopulation is re-diversified to enhance its global search capability. Our experimental results and analysis suggest that the new CC algorithm can improve the performance of CC and serves as a competitive solver for large-scale optimization problems. [ABSTRACT FROM AUTHOR]

This letter pays attention to the mitigation of the radio frequency interference (RFI) sources located at coastal regions for synthetic aperture interferometric radiometer (SAIR). To remove an RFI at the visibility level, it will be necessary to estimate the brightness temperature (BT) of the point source, which is currently done by computing the median of the surrounded pixels to get the background BT and subtracting it from the original contaminated BT. However, this strategy is based on the assumption that the background BT distribution around the RFI is flat, and this is not reasonable for those RFIs from coastal cities and could result in estimation deviation. A robust RFI mitigation method is proposed without introducing complex computing. Instead of focusing only on the local area, the basic idea of our method is to step into the wide area and minimize the overall fluctuation of the pixels affected by the RFI in the BT image. The method tests based on SMOS visibility samples validate the correctness of the developed method. [ABSTRACT FROM AUTHOR]

The capacitated arc routing problem (CARP) is a challenging combinatorial optimization problem abstracted from many real-world applications, such as waste collection, road gritting, and mail delivery. However, few studies considered dynamic changes during the vehicles’ service, which can cause the original schedule infeasible or obsolete. The few existing studies are limited by the dynamic scenarios considered, and by overly complicated algorithms that are unable to benefit from the wealth of contributions provided by the existing CARP literature. In this article, we first provide a mathematical formulation of dynamic CARP (DCARP) and design a simulation system that is able to consider dynamic events while a routing solution is already partially executed. We then propose a novel framework which can benefit from the existing static CARP optimization algorithms so that they could be used to handle DCARP instances. The framework is very flexible. In response to a dynamic event, it can use either a simple restart strategy or a sequence transfer strategy that benefits from the past optimization experience. Empirical studies have been conducted on a wide range of DCARP instances to evaluate our proposed framework. The results show that the proposed framework significantly improves over state-of-the-art dynamic optimization algorithms. [ABSTRACT FROM AUTHOR]

Knee points, characterized as a small improvement on one objective can lead to a significant degradation on at least one of the other objectives, are attractive to decision makers (DMs) in multicriterion decision making. This article presents a simple and effective knee point identification (KPI) method to help DMs identify solution(s) of interest from a given set of tradeoff solutions thus facilitating posterior decision making. Our basic idea is to sequentially validate whether a solution is a knee point or not by comparing its localized tradeoff utility with others within its neighborhood characterized from a decomposition perspective. In particular, a solution is a knee point if and only if it has the best-localized tradeoff utility among its neighbors. We implement a GPU version that carries out the KPI in a parallel manner. This GPU version reduces the worst-case complexity from quadratic to linear. The performance of our proposed method is compared with five state-of-the-art KPI methods on 134 test problem instances and two real-world engineering design problems. Empirical results demonstrate its outstanding performance especially on problems with many local knee points. We further validate the usefulness of our proposed method for guiding evolutionary multiobjective optimization algorithms to search for knee points on the fly during the evolutionary process. [ABSTRACT FROM AUTHOR]

Time Delay Reservoir (TDR) is a hardware-friendly machine learning approach from two perspectives. First, it can prevent the connection overhead of neural networks with increasing neurons. Second, through its dynamic system representation, TDR can also be implemented in hardware by different systems. However, it performs poorly on tasks that involve long-term dependency. In this work, we first introduce a higher-order delay unit, which is capable of accumulating and transferring the long history states in an adaptive manner to further enhance the reservoir memory. Particle Swarm Optimisation is applied to optimize the enhanced degree of memory adaptivity. Our experiments demonstrate its superiority both for short- and long-term memory datasets over seven existing approaches. In light of the hardware-friendly feature of TDR, we further propose a memristive implementation of our adaptive memory-enhanced TDR, where a dynamic memristor and the memristor-based delay element are applied to construct the reservoir. Through circuit simulation, the feasibility of our proposed memristive implementation is verified. The comparisons with different hardware reservoirs show that our proposed memristive implementation is effective both for short- and long-term memory datasets, while exhibiting benefits in terms of smaller circuit area and lower power consumption compared with traditional hardware reservoirs. [ABSTRACT FROM AUTHOR]