Neural solvers have demonstrated remarkable success in combinatorial optimization, often surpassing traditional heuristics in speed, solution quality, and generalization. However, their efficacy deteriorates significantly when confronted with complex constraints that cannot be effectively managed through simple masking mechanisms. To address this limitation, we introduce Universal Constrained Preference Optimization (UCPO), a novel plug-and-play framework that seamlessly integrates preference learning into existing neural solvers via a specially designed loss function, without requiring architectural modifications. UCPO embeds constraint satisfaction directly into a preference-based objective, eliminating the need for meticulous hyperparameter tuning. Leveraging a lightweight warm-start fine-tuning protocol, UCPO enables pre-trained models to consistently produce near-optimal, feasible solutions on challenging constraint-laden tasks, achieving exceptional performance with as little as 1% of the original training budget.

Entity alignment (EA) is a fundamental task in knowledge graph (KG) integration, aiming to identify equivalent entities across different KGs for a unified and comprehensive representation. Recent advances have explored pre-trained language models (PLMs) to enhance the semantic understanding of entities, achieving notable improvements. However, existing methods face two major limitations. First, they rely heavily on human-annotated labels for training, leading to high computational costs and poor scalability. Second, some approaches use large language models (LLMs) to predict alignments in a multi-choice question format, but LLM outputs may deviate from expected formats, and predefined options may exclude correct matches, leading to suboptimal performance. To address these issues, we propose LEA, an LLM-augmented entity alignment framework that eliminates the need for labeled data and enhances robustness by mitigating information heterogeneity at both embedding and semantic levels. LEA first introduces an entity textualization module that transforms structural and textual information into a unified format, ensuring consistency and improving entity representations. It then leverages LLMs to enrich entity descriptions, enhancing semantic distinctiveness. Finally, these enriched descriptions are encoded into a shared embedding space, enabling efficient alignment through text retrieval techniques. To balance performance and computational cost, we further propose a selective augmentation strategy that prioritizes the most ambiguous entities for refinement. Experimental results on both homogeneous and heterogeneous KGs demonstrate that LEA outperforms existing models trained on 30 % labeled data, achieving a 30 % absolute improvement in Hit@1 score. As LLMs and text embedding models advance, LEA is expected to further enhance EA performance, providing a scalable and robust paradigm for practical applications. The code and dataset can be found at https://github.com/Longmeix/LEA.

Recent decomposition-based neural multi-objective combinatorial optimization (MOCO) methods struggle to achieve desirable performance. Even equipped with complex learning techniques, they often suffer from significant optimality gaps in weight-specific subproblems. To address this challenge, we propose a neat weight embedding method to learn weight-specific representations, which captures weight-instance interaction for the subproblems and was overlooked by most current methods. We demonstrate the potentials of our method in two instantiations. First, we introduce a succinct addition model to learn weight-specific node embeddings, which surpassed most existing neural methods. Second, we design an enhanced conditional attention model to simultaneously learn the weight embedding and node embeddings, which yielded new state-of-the-art performance. Experimental results on classic MOCO problems verified the superiority of our method. Remarkably, our method also exhibits favorable generalization performance across problem sizes, even outperforming the neural method specialized for boosting size generalization.

Existing neural multi-objective combinatorial optimization (MOCO) methods still exhibit an optimality gap since they fail to fully exploit the intrinsic features of problem instances. A significant factor contributing to this shortfall is their reliance solely on graph-modal information. To overcome this, we propose a novel graph-image multimodal fusion (GIMF) framework that enhances neural MOCO methods by integrating graph and image information of the problem instances. Our GIMF framework comprises three key components: (1) a constructed coordinate image to better represent the spatial structure of the problem instance, (2) a problem-size adaptive resolution strategy during the image construction process to improve the cross-size generalization of the model, and (3) a multimodal fusion mechanism with modality-specific bottlenecks to efficiently couple graph and image information. We demonstrate the versatility of our GIMF by implementing it with two state-of-the-art neural MOCO backbones. Experimental results on classic MOCO problems show that our GIMF significantly outperforms state-of-the-art neural MOCO methods and exhibits superior generalization capability.

Neural Combinatorial Optimization (NCO) has emerged as a promising approach for NP-hard problems. However, prevailing RL-based methods suffer from low sample efficiency due to sparse rewards and underused solutions. We propose Best-anchored and Objective-guided Preference Optimization (BOPO), a training paradigm that leverages solution preferences via objective values. It introduces: (1) a best-anchored preference pair construction for better explore and exploit solutions, and (2) an objective-guided pairwise loss function that adaptively scales gradients via objective differences, removing reliance on reward models or reference policies. Experiments on Job-shop Scheduling Problem (JSP), Traveling Salesman Problem (TSP), and Flexible Job-shop Scheduling Problem (FJSP) show BOPO outperforms state-of-the-art neural methods, reducing optimality gaps impressively with efficient inference. BOPO is architecture-agnostic, enabling seamless integration with existing NCO models, and establishes preference optimization as a principled framework for combinatorial optimization.

Pedestrian trajectory prediction aims to forecast future trajectories based on observed behaviors and surrounding conditions, and it is critical for applications like autonomous driving. Predicting trajectories in unseen scenes is challenging due to varying environments, elusive internal movement patterns, and complex social interactions. Existing methods face two limitations. Firstly, they struggle to effectively extract internal movement patterns from historical trajectories without labeled samples, which are often inaccessible in practice. Secondly, they fail to learn social interaction patterns across scenes, particularly when using angle-related features that are noise-sensitive and not strictly invariant to Euclidean transformations. To address these challenges, this paper introduces a Geometry-guided Behavior Pattern Adaptation (GBPA) method based on two geometric observations. Firstly, properly normalized historical trajectories are distributionally similar to full trajectories, allowing generation of pseudo-full trajectories for auxiliary training. Secondly, the discretized angular partitions, created by splitting the perceptive field into equal-sized fans, are invariant to Euclidean transformations and robust to noise. GBPA employs a test-time training strategy on scaled historical trajectories (T3SH) to adapt internal movement patterns without future trajectories and an angular partitioned attention (APA) mechanism to capture transferable social interaction patterns by differentiating neighbors’ effects. Experimental results on two datasets demonstrate that GBPA significantly improves prediction performance.

Emergence, a global property of complex adaptive systems (CASs) constituted by interactive agents, is prevalent in real-world dynamic systems, e.g., network-level traffic congestions. Detecting its formation and evaporation helps to monitor the state of a system, allowing it to issue a warning signal for harmful emergent phenomena. Since there is no centralized controller of CAS, detecting emergence based on each agent's local observation is desirable but challenging. Existing works are unable to capture emergence-related spatial patterns, and fail to model the nonlinear relationships among agents. This article proposes a hierarchical framework with spatio-temporal consistency learning (HSTCL) to solve these two problems by learning the system representation and agent representations, respectively. Spatio-temporal encoders (STEs) composed of spatial and temporal transformers are designed to capture agents' nonlinear relationships and the system's complex evolution. Agents' and the system's representations are learned to preserve the spatio-temporal consistency by minimizing the spatial and temporal dissimilarities in a self-supervised manner in the latent space. Our method achieves more accurate detection than traditional methods and deep learning methods on three datasets with well-known yet hard-to-detect emergent behaviors. Notably, our hierarchical framework is generic in incorporating other deep learning methods for agent-level and system-level detection.

Whole slide image (WSI) classification is one of the important fields of digital pathology, and is generally solved as a weakly supervised learning problem by adopting multiple instance learning (MIL). However, a common but crucial challenge faced by existing MIL models is their inability to provide convincing explanations that can win the trust of pathologists and be applied to clinical diagnosis. In addition, most attention-based MIL models use attention scores to represent the importance of each patch in the WSI rather than inferring patch probabilities directly, which does not accurately detect the critical patches. To address these two challenges, we propose a ProtoTree based MIL model for WSI classification, called ProtoTree-MIL, where ProtoTree is an interpretable model that combines the advantages of prototype-learning and decision tree. ProtoTree-MIL not only explains why some patches are important for the final prediction through prototype-learning, but also provides global and local explanation through decision tree. We also propose a method to infer patch probabilities and measure their importance under the framework of ProtoTree-MIL. By conducting various experiments on three public WSI datasets, Camelyon16, TCGA-NSCLC, and TCGA-RCC, we demonstrate that our proposed ProtoTree-MIL can achieve a competitive performance to the state-of-the-art MIL models but provide more persuasive explanations than them. Explicitly generating patch probabilities also makes ProtoTree-MIL more accurate to detect the key patches than other attention-based MIL models. Specially, by evaluating our model on a real clinical gastritis and gastric cancer dataset, we show the explanations provided by ProtoTree-MIL are significant and faithful.

We consider the robust routing problem with uncertain travel times under the min-max regret criterion, which represents an extended and robust version of the classic traveling salesman problem (TSP) and vehicle routing problem (VRP). The general budget uncertainty set is employed to capture the uncertainty, which provides the capability to control the conservatism of obtained solutions and covers the commonly used interval uncertainty set as a special case. The goal is to obtain a robust solution that minimizes the maximum deviation from the optimal routing time in the worst-case scenario. Given the significant advancements and broad applications of neural combinatorial optimization methods in recent years, we present our initial attempt to combine neural approaches for solving this problem. We propose a dual multi-head cross attention mechanism to extract problem features represented by the inputted uncertainty sets. To tackle the built-in maximization problem, we derive the regret value by invoking a pre-trained model, subsequently utilizing it as the reward during the model training. Our experimental results on the robust TSP and VRP demonstrate the efficacy of our neural combinatorial optimization method, showcasing its ability to efficiently handle the robust routing problem of various sizes within a shorter time compared with alternative heuristic approaches.

We explore the robust traveling salesman problem (RTSP) with interval uncertainty under the min-max regret criterion, which enhances the classic traveling salesman problem (TSP) by focusing on robustness. Our aim is to develop a conservative solution that minimizes the maximum deviation from the optimal routing time in the worst-case scenario. To achieve this, we integrate neural models into heuristic approaches, capitalizing on recent advancements in neural techniques. Specifically, we incorporate a pre-trained neural model into the tabu search framework, using it to refine the evaluation function. This novel integration streamlines the solution improvement process. Our experimental results underscore the effectiveness of this approach, showing that it handles various scales of the robust traveling salesman problem more efficiently and in less time compared to traditional heuristic methods.

Dynamical complex systems composed of interactive heterogeneous agents are prevalent in the world, including urban traffic systems and social networks. Modeling the interactions among agents is the key to understanding and predicting the dynamics of the complex system, e.g., predicting the trajectories of traffic participants in the city. Compared with interaction modeling in homogeneous systems such as pedestrians in a crowded scene, heterogeneous interaction modeling is less explored. Worse still, the error accumulation problem becomes more severe since the interactions are more complex. To tackle the two problems, this article proposes heterogeneous interaction modeling with reduced accumulated error (HIMRAE) for multiagent trajectory prediction. Based on the historical trajectories, our method infers the dynamic interaction graphs among agents, featured by directed interacting relations and interacting effects. A heterogeneous attention mechanism (HAM) is defined on the interaction graphs for aggregating the influence from heterogeneous neighbors to the target agent. To alleviate the error accumulation problem, this article analyzes the error sources from the spatial and temporal perspectives, and proposes to introduce the graph entropy and the mixup training strategy for reducing the two types of errors, respectively. Our method is examined on three real-world datasets containing heterogeneous agents, and the experimental results validate the superiority of our method.

Adversarial attacks on deep neural networks keep raising security concerns in natural language processing research.Existing defenses focus on improving the robustness of the victim model in the training stage.However, they often neglect to proactively mitigate adversarial attacks during inference.Towards this overlooked aspect, we propose a defense framework that aims to mitigate attacks by confusing attackers and correcting adversarial contexts that are caused by malicious perturbations.Our framework comprises three components: (1) a synonym-based transformation to randomly corrupt adversarial contexts in the word level, (2) a developed BERT defender to correct abnormal contexts in the representation level, and (3) a simple detection method to filter out adversarial examples, any of which can be flexibly combined.Additionally, our framework helps improve the robustness of the victim model during training.Extensive experiments demonstrate the effectiveness of our framework in defending against word-level adversarial attacks.

Zhaoyang Wang, Shaohan Huang, Yuxuan Liu, Jiahai Wang, Minghui Song, Zihan Zhang, Haizhen Huang, Furu Wei, Weiwei Deng, Feng Sun, Qi Zhang. Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing. 2023.

Knowledge graph (KG) is receiving increasing attention from researchers in recommender systems with the help of graph neural networks (GNN). Beyond accuracy, diversity of recommendation is also recognized as a key factor in broadening users’ horizons and boosting satisfaction for users. Considering diversity adapted to user demands can facilitate the recommendation performance for both accuracy and diversity. However, most approaches fail to (1) explore the help of KG for diversity, and (2) identify different kinds of latent interests from users for diversity. This paper proposes a diversity-enhanced recommendation with knowledge-aware interests. The user interest consists of devoted interest and diverse interest in our approach modeled by a dual-branch GNN-based learning structure with an adaptive trade-off. The devoted interest learning branch exploits the entity relations from KG to explore the potential patterns of users to improve accuracy, while the diverse interest learning branch additionally combines the category of the items with KG to achieve diversity. Attentive relational aggregation is designed to aggregate the information from KG and user-item interaction for the representations of users and items modeling. Extensive experiments on three real-world datasets show that our approach effectively improves the recommendation accuracy while obtaining impressive diversity. This work is available at https://github.com/ljf012/DERK.

Recently, neural heuristics based on deep reinforcement learning have exhibited promise in solving multi-objective combinatorial optimization problems (MOCOPs). However, they are still struggling to achieve high learning efficiency and solution quality. To tackle this issue, we propose an efficient meta neural heuristic (EMNH), in which a meta-model is first trained and then fine-tuned with a few steps to solve corresponding single-objective subproblems. Specifically, for the training process, a (partial) architecture-shared multi-task model is leveraged to achieve parallel learning for the meta-model, so as to speed up the training; meanwhile, a scaled symmetric sampling method with respect to the weight vectors is designed to stabilize the training. For the fine-tuning process, an efficient hierarchical method is proposed to systematically tackle all the subproblems. Experimental results on the multi-objective traveling salesman problem (MOTSP), multi-objective capacitated vehicle routing problem (MOCVRP), and multi-objective knapsack problem (MOKP) show that, EMNH is able to outperform the state-of-the-art neural heuristics in terms of solution quality and learning efficiency, and yield competitive solutions to the strong traditional heuristics while consuming much shorter time.

Most of existing neural methods for multi-objective combinatorial optimization (MOCO) problems solely rely on decomposition, which often leads to repetitive solutions for the respective subproblems, thus a limited Pareto set. Beyond decomposition, we propose a novel neural heuristic with diversity enhancement (NHDE) to produce more Pareto solutions from two perspectives. On the one hand, to hinder duplicated solutions for different subproblems, we propose an indicator-enhanced deep reinforcement learning method to guide the model, and design a heterogeneous graph attention mechanism to capture the relations between the instance graph and the Pareto front graph. On the other hand, to excavate more solutions in the neighborhood of each subproblem, we present a multiple Pareto optima strategy to sample and preserve desirable solutions. Experimental results on classic MOCO problems show that our NHDE is able to generate a Pareto front with higher diversity, thereby achieving superior overall performance. Moreover, our NHDE is generic and can be applied to different neural methods for MOCO.

Feature selection (FS) has received significant attention since the use of a well-selected subset of features may achieve better classification performance than that of full features in many real-world applications. It can be considered as a multiobjective optimization consisting of two objectives: 1) minimizing the number of selected features and 2) maximizing classification performance. Ant colony optimization (ACO) has shown its effectiveness in FS due to its problem-guided search operator and flexible graph representation. However, there lacks an effective ACO-based approach for multiobjective FS to handle the problematic characteristics originated from the feature interactions and highly discontinuous Pareto fronts. This article presents an Information-theory-based Nondominated Sorting ACO (called INSA) to solve the aforementioned difficulties. First, the probabilistic function in ACO is modified based on the information theory to identify the importance of features; second, a new ACO strategy is designed to construct solutions; and third, a novel pheromone updating strategy is devised to ensure the high diversity of tradeoff solutions. INSA's performance is compared with four machine-learning-based methods, four representative single-objective evolutionary algorithms, and six state-of-the-art multiobjective ones on 13 benchmark classification datasets, which consist of both low and high-dimensional samples. The empirical results verify that INSA is able to obtain solutions with better classification performance using features whose count is similar to or less than those obtained by its peers.

Constrained multiobjective optimization problems widely exist in real-world applications. To handle them, the balance between constraints and objectives is crucial, but remains challenging due to non-negligible impacts of problem types. In our context, the problem types refer particularly to those determined by the relationship between the constrained Pareto-optimal front (PF) and the unconstrained PF. Unfortunately, there has been little awareness on how to achieve this balance when faced with different types of problems. In this article, we propose a new constraint handling technique (CHT) by taking into account potential problem types. Specifically, inspired by the prior work, problems are classified into three primary types: 1) I; 2) II; and 3) III, with the constrained PF being made up of the entire, part and none of the unconstrained counterpart, respectively. Clearly, any problem must be one of the three types. For each possible type, there exists a tailored mechanism being used to handle the relationships between constraints and objectives (i.e., constraint priority, objective priority, or the switch between them). It is worth mentioning that exact problem types are not required because we just consider their possibilities in the new CHT. Conceptually, we show that the new CHT can make a tradeoff among different types of problems. This argument is confirmed by experimental studies performed on 38 benchmark problems, whose types are known, and a real-world problem (with unknown types) in search-based software engineering. Results demonstrate that within both decomposition-based and nondecomposition-based frameworks, the new CHT can indeed achieve a good tradeoff among different problem types, being better than several state-of-the-art CHTs.

A single dendritic neuron model (DNM) that owns the nonlinear information processing ability of dendrites has been widely used for classification and prediction. Complex-valued neural networks that consist of a number of multiple/deep-layer McCulloch-Pitts neurons have achieved great successes so far since neural computing was utilized for signal processing. Yet no complex value representations appear in single neuron architectures. In this article, we first extend DNM from a real-value domain to a complex-valued one. Performance of complex-valued DNM (CDNM) is evaluated through a complex XOR problem, a non-minimum phase equalization problem, and a real-world wind prediction task. Also, a comparative analysis on a set of elementary transcendental functions as an activation function is implemented and preparatory experiments are carried out for determining hyperparameters. The experimental results indicate that the proposed CDNM significantly outperforms real-valued DNM, complex-valued multi-layer perceptron, and other complex-valued neuron models.

A traveling salesman problem (TSP) is a well-known NP-complete problem. Traditional TSP presumes that the locations of customers and the traveling time among customers are fixed and constant. In real-life cases, however, the traffic conditions and customer requests may change over time. To find the most economic route, the decisions can be made constantly upon the time-point when the salesman completes his service of each customer. This brings in a dynamic version of the traveling salesman problem (DTSP), which takes into account the information of real-time traffic and customer requests. DTSP can be extended to a dynamic pickup and delivery problem (DPDP). In this article, we ameliorate the attention model to make it possible to perceive environmental changes. A deep reinforcement learning algorithm is proposed to solve DTSP and DPDP instances with a size of up to 40 customers in 100 locations. Experiments show that our method can capture the dynamic changes and produce a highly satisfactory solution within a very short time. Compared with other baseline approaches, more than 5% improvements can be observed in many cases.

Aspect extraction is one of the key tasks in fine-grained sentiment analysis. This task aims to identify explicit opinion targets from user-generated documents. Currently, the mainstream methods for aspect extraction are built on recurrent neural networks (RNNs), which are difficult to parallelize. To accelerate the training/testing process, convolutional neural network (CNN)-based methods are introduced. However, such models usually utilize the same set of filters to convolve all input documents, and hence, the unique information inherent in each document may not be fully captured. To alleviate this issue, we propose a CNN-based model that employs a set of dynamic filters. Specifically, the proposed model extracts the aspects in a document using the filters generated from the aspect information intrinsic in the document. With the dynamically generated filters, our model is capable of learning more important features concerning aspects, thus promoting the effectiveness of aspect extraction. Furthermore, considering that aspects can be grouped into certain topics that conversely indicate the target words that need to be extracted, we naturally introduce a neural topic model (NTM) and integrate latent topics into the CNN-based module to help identify aspects. Experiments on two benchmark datasets demonstrate that the joint model is able to effectively identify aspects and produce interpretable topics.

Deep reinforcement learning (DRL) has recently shown its success in tackling complex combinatorial optimization problems. When these problems are extended to multiobjective ones, it becomes difficult for the existing DRL approaches to flexibly and efficiently deal with multiple subproblems determined by the weight decomposition of objectives. This article proposes a concise meta-learning-based DRL approach. It first trains a meta-model by meta-learning. The meta-model is fine-tuned with a few update steps to derive submodels for the corresponding subproblems. The Pareto front is then built accordingly. Compared with other learning-based methods, our method can greatly shorten the training time of multiple submodels. Due to the rapid and excellent adaptability of the meta-model, more submodels can be derived so as to increase the quality and diversity of the found solutions. The computational experiments on multiobjective traveling salesman problems and multiobjective vehicle routing problems with time windows demonstrate the superiority of our method over most of the learning-based and iteration-based approaches.

Emotion cause analysis (ECA) aims to extract emotion clauses and find the corresponding cause of the emotion. Existing methods adopt fine-tuning paradigm to solve certain types of ECA tasks. These task-specific methods have a deficiency of universality. And the relations among multiple objectives in one task are not explicitly modeled. Moreover, the relative position information introduced in most existing methods may make the model suffer from dataset bias. To address the first two problems, this paper proposes a universal prompt tuning method to solve different ECA tasks in the unified framework. As for the third problem, this paper designs a directional constraint module and a sequential learning module to ease the bias. Considering the commonalities among different tasks, this paper proposes a cross-task training method to further explore the capability of the model. The experimental results show that our method achieves competitive performance on the ECA datasets.

Tabular and textual question answering requires systems to perform reasoning over heterogeneous information, considering table structure, and the connections among table and text. In this paper, we propose a ChAin-centric Reasoning and Pre-training framework (CARP). CARP utilizes hybrid chain to model the explicit intermediate reasoning process across table and text for question answering. We also propose a novel chain-centric pre-training method, to enhance the pre-trained model in identifying the cross-modality reasoning process and alleviating the data sparsity problem. This method constructs the large-scale reasoning corpus by synthesizing pseudo heterogeneous reasoning paths from Wikipedia and generating corresponding questions. We evaluate our system on OTT-QA, a large-scale table-and-text open-domain question answering benchmark, and our system achieves the state-of-the-art performance. Further analyses illustrate that the explicit hybrid chain offers substantial performance improvement and interpretablity of the intermediate reasoning process, and the chain-centric pre-training boosts the performance on the chain extraction.

Vehicle routing problem with time windows (VRPTW) is an important topic in modern delivery companies. Optimizing the vehicle routes not only reduces the transportation cost but also increases the customers' satisfaction. In literature, there are many studies focusing on symmetric vehicle routing problems. However, due to the transportation network and traffic conditions, the traveling distance and traveling time may be asymmetric in practical scenarios. In this paper, we formulate a practical VRPTW from the perspective of edges. With the edge-based formulation, a novel deep reinforcement learning model based on graph attention network is proposed. Two benchmark sets of practical VRPTW for training and testing are generated from the real-world data. The experimental results on the benchmark sets demonstrate that our method can outperform node-based and other well-known methods.

Wanjun Zhong, Yifan Gao, Ning Ding, Yujia Qin, Zhiyuan Liu, Ming Zhou, Jiahai Wang, Jian Yin, Nan Duan. Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2022.

Recent neural methods for vehicle routing problems always train and test the deep models on the same instance distribution (i.e., uniform). To tackle the consequent cross-distribution generalization concerns, we bring the knowledge distillation to this field and propose an Adaptive Multi-Distribution Knowledge Distillation (AMDKD) scheme for learning more generalizable deep models. Particularly, our AMDKD leverages various knowledge from multiple teachers trained on exemplar distributions to yield a light-weight yet generalist student model. Meanwhile, we equip AMDKD with an adaptive strategy that allows the student to concentrate on difficult distributions, so as to absorb hard-to-master knowledge more effectively. Extensive experimental results show that, compared with the baseline neural methods, our AMDKD is able to achieve competitive results on both unseen in-distribution and out-of-distribution instances, which are either randomly synthesized or adopted from benchmark datasets (i.e., TSPLIB and CVRPLIB). Notably, our AMDKD is generic, and consumes less computational resources for inference.

The multiobjective combinatorial optimization problems (MOCOPs) have a wide range of real-world applications. Designing an effective algorithm has an important and practical significance. Due to the huge search space and limited time, it is generally difficult to obtain the optimal solution of this kind of problem by traditional exact and heuristic algorithms. Recently, learning-based algorithms have achieved good results in solving MOCOPs, but the quality and diversity of found solutions can be further improved. In this paper, we propose a Weight-Specific-Decoder Attention Model (WSDAM) to better approximate the whole Pareto set. It embeds a weight-adaptive layer into the decoder to concentrate on the information of different weight vectors. During the model training, the weight vector is sampled from the Dirichlet distribution, which can further strengthen the learning of boundary solutions. We evaluate our method on two classic MOCOPs, i.e., the multiobjective traveling salesman problem (MOTSP) and multiobjective capacitated vehicle routing problem (MOCVRP). The experimental results show that our proposed method outperforms current state-of-the-art learning-based methods in both solution quality and generalization ability.

There are many combinatorial optimization problems derived from the classic traveling salesman problem (TSP). The quadratic traveling salesman problem (QTSP) is one of them. It needs to consider the relationship between three successive nodes rather than two successive nodes. In literature, there are exact methods based on integer programming and approximate methods based on heuristics for solving QTSP. In this paper, we try to adopt deep reinforcement learning to tackle QTSP. We consider two classic QTSPs studied in the previous literature, namely the angular-metric TSP and the angular-distance-metric TSP. Both of them consider the turning angle for each node, and the angular-distance-metric TSP further considers the total traveling distance in the original TSP. The experimental results show that our method is superior to some typical heuristic methods in terms of solution quality, and better than the exact methods in terms of time.

Motivated by some practical applications in urban services such as water sparkling, we study a split-delivery capacitated arc-routing problem with time windows (SDCARPTW). It is a variant of arc-routing problem and is defined on an undirected graph where the demands on the arcs are splitable, and time window and capacity constraints must be satisfied. We propose a mathematical formulation for SDCARPTW and derive some nice properties of the split-delivery structure, which can help to well represent a solution of SDCARPTW. The dynamic programming, neighborhood search and perturbation process are combined to develop a tabu search algorithm. Through computational studies on CARPTW benchmark datasets, we validate the effectiveness and efficiency of our proposed algorithm. New datasets for SDCARPTW are further proposed and the impact of the split-delivery option is analyzed.

Convergence, diversity and feasibility are three important issues when solving constrained multiobjective optimization problems (CMOPs). To deal with the balance among convergence, diversity and feasibility well, this article proposes a cooperative multiobjective evolutionary algorithm with propulsive population (CMOEA-PP) for solving CMOPs. CMOEA-PP has two populations, including propulsive population and normal population, and these two populations work cooperatively. Specifically, propulsive population focuses on convergence. Normal population gives priority to feasibility and is obligated to maintain diversity. To cross through the infeasible region and reach the Pareto front (PF), propulsive population does not consider constraints in the early stage and only considers constraints in the later stage. To further accelerate the speed of convergence, propulsive population only searches for corner solutions and center solutions, while normal population searches for the whole PF. As a result, propulsive population can cross through the infeasible region because of the lack of attention to feasibility. In addition, propulsive population also can guide and accelerate the convergence of the evolutionary process. Comprehensive experiment results on several sets of benchmark problems demonstrate that CMOEA-PP is better than existing state-of-the-art competitors.

Many complex processes can be viewed as dynamical systems of interacting agents. In many cases, only the state sequences of individual agents are observed, while the interacting relations and the dynamical rules are unknown. The neural relational inference (NRI) model adopts graph neural networks that pass messages over a latent graph to jointly learn the relations and the dynamics based on the observed data. However, NRI infers the relations independently and suffers from error accumulation in multi-step prediction at dynamics learning procedure. Besides, relation reconstruction without prior knowledge becomes more difficult in more complex systems. This paper introduces efficient message passing mechanisms to the graph neural networks with structural prior knowledge to address these problems. A relation interaction mechanism is proposed to capture the coexistence of all relations, and a spatio-temporal message passing mechanism is proposed to use historical information to alleviate error accumulation. Additionally, the structural prior knowledge, symmetry as a special case, is introduced for better relation prediction in more complex systems. The experimental results on simulated physics systems show that the proposed method outperforms existing state-of-the-art methods.

Generating text with high quality and sufficient diversity is a fundamental task in natural language generation. Although generative adversarial networks (GANs) achieve promising results in text generation, GAN-based language models suffer from mode collapse, i.e., the generator tends to sacrifice diversity and focus on limited text patterns with high quality. By contrast, maximum likelihood estimation (MLE) based language models could cover various text patterns and generate diversified samples with poor quality. This paper proposes a cooperative framework with GANs and entropic auto-encoders (EAEs), named GAN-EAE, to synthesize their advantages for text generation, where EAEs are powerful MLE-based generative models based on deterministic auto-encoders. By imitating the output distribution of EAEs, the generator shapes its output distribution closer to the real data distribution against mode collapse. Meanwhile, by learning the samples from the generator of GANs, EAEs subtly distribute probability mass on high quality patterns for improving generation quality. The similar samples obtained from the generator may raise mode collapse and should be downplayed during adversarial training. Thus, a sample re-weighting mechanism is adopted to improve diversity by measuring the inner distance of generated samples. Experimental results demonstrate that GAN-EAE could improve both GANs and EAEs to achieve state-of-the-art performance.

Learning-based heuristics for solving combinatorial optimization problems has recently attracted much academic attention. While most of the existing works only consider the single objective problem with simple constraints, many real-world problems have the multiobjective perspective and contain a rich set of constraints. This paper proposes a multiobjective deep reinforcement learning with evolutionary learning algorithm for a typical complex problem called the multiobjective vehicle routing problem with time windows (MO-VRPTW). In the proposed algorithm, the decomposition strategy is applied to generate subproblems for a set of attention models. The comprehensive context information is introduced to further enhance the attention models. The evolutionary learning is also employed to fine-tune the parameters of the models. The experimental results on MO-VRPTW instances demonstrate the superiority of the proposed algorithm over other learning-based and iterative-based approaches.

Traveling Salesman Problem (TSP) is a well-known NP-hard combinatorial optimization problem. Recently, many researchers have used deep reinforcement learning to solve it. However, traffic factors are rarely considered in their works, in which the traveling time between customer locations is assumed to be constant over the planning horizon. For many practical scenarios, the traffic conditions between customer locations may change over time due to the impact of traffic patterns. Thus, this paper considers a Time-Dependent Traveling Salesman Problem with Time Windows (TDTSPTW), where the time dependency is obtained by fitting the collected traffic data into real-time traffic function with the interpolation method. We propose a deep reinforcement learning framework to solve TDTSPTW. Extensive experiments on TDTSPTW instances indicate that the proposed method can capture the real-time traffic changes and yield high-quality solutions within a very short time, compared with other typical baseline algorithms.

This paper presents an arc-routing problem with time-dependent penalty cost (ARPTPC), which arises from a practical application in garbage collection service. ARPTPC considers the minimization of service cost, traveling cost and penalty cost. While the first two parts are known as the traditional objectives of arc-routing problems, the third part is determined by the parking pattern and service period on each arc. We formulate the problem by using a mixed integer linear model. To solve it, we design a dynamic programming to determine the optimal service beginning time on each edge when a routing sequence is given. We then propose a problem-specific intelligent heuristic search approach involving six neighborhood operators, a priority maintenance mechanism and a perturbation process. Through numerical experiments, we demonstrate that the proposed approach is able to produce satisfactory solutions of ARPTPC. Additional experiments are also carried out to analyze the effects of operators and parameters on solution quality.

JADE is a differential evolution (DE) algorithm and has been shown to be very competitive in comparison with other evolutionary optimization algorithms. However, it suffers from the premature convergence problem and is easily trapped into local optima. This article presents a novel JADE variant by incorporating chaotic local search (CLS) mechanisms into JADE to alleviate this problem. Taking advantages of the ergodicity and nonrepetitious nature of chaos, it can diversify the population and thus has a chance to explore a huge search space. Because of the inherent local exploitation ability, its embedded CLS can exploit a small region to refine solutions obtained by JADE. Hence, it can well balance the exploration and exploitation in a search process and further improve its performance. Four kinds of its CLS incorporation schemes are studied. Multiple chaotic maps are individually, randomly, parallelly, and memory-selectively incorporated into CLS. Experimental and statistical analyses are performed on a set of 53 benchmark functions and four real-world optimization problems. Results show that it has a superior performance in comparison with JADE and some other state-of-the-art optimization algorithms.

This paper introduces a multiobjective fleet size and mix location-routing problem with time windows and designs a set of real-world benchmark instances. Then, two versions of multiobjective multiple neighborhood search algorithms based on decomposition and vector angle are developed for solving the problem. In the proposed algorithms, three different kinds of neighborhood search operators, including general local search, objective-specific local search, and large neighborhood search, are carefully designed and combined in a synergistic manner. The experimental results show the effectiveness of the proposed algorithms. Relationships between different objectives in this multiobjective problem are also discussed.

In this paper, we propose an enhanced branch-and-bound (B&B) framework for a class of sequencing problems, which aim to find a permutation of all involved elements to minimize a given objective function. We require that the sequencing problems satisfy three conditions: 1) incrementally computable; 2) monotonic; and 3) overlapping subproblems. Our enhanced B&B framework is built on the classical B&B process by introducing two techniques, i.e., dominance rules and caching search states. Following the enhanced B&B framework, we conduct empirical studies on three typical and challenging sequencing problems, i.e., quadratic traveling salesman problem, traveling repairman problem, and talent scheduling problem. The computational results demonstrate the effectiveness of our enhanced B&B framework when compared to classical B&B and some exact approaches, such as dynamic programming and constraint programming. Additional experiments are carried out to analyze different configurations of the algorithm.

Generating multiple categories of texts is a challenging task and draws more and more attention. Since generative adversarial nets (GANs) have shown competitive results on general text generation, they are extended for category text generation in some previous works. However, the complicated model structures and learning strategies limit their performance and exacerbate the training instability. This paper proposes a category-aware GAN (CatGAN) which consists of an efficient category-aware model for category text generation and a hierarchical evolutionary learning algorithm for training our model. The category-aware model directly measures the gap between real samples and generated samples on each category, then reducing this gap will guide the model to generate high-quality category samples. The Gumbel-Softmax relaxation further frees our model from complicated learning strategies for updating CatGAN on discrete data. Moreover, only focusing on the sample quality normally leads the mode collapse problem, thus a hierarchical evolutionary learning algorithm is introduced to stabilize the training procedure and obtain the trade-off between quality and diversity while training CatGAN. Experimental results demonstrate that CatGAN outperforms most of the existing state-of-the-art methods.

Wanjun Zhong, Duyu Tang, Zhangyin Feng, Nan Duan, Ming Zhou, Ming Gong, Linjun Shou, Daxin Jiang, Jiahai Wang, Jian Yin. Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics. 2020.

Fact checking is a challenging task because verifying the truthfulness of a claim requires reasoning about multiple retrievable evidence.In this work, we present a method suitable for reasoning about the semantic-level structure of evidence.Unlike most previous works, which typically represent evidence sentences with either string concatenation or fusing the features of isolated evidence sentences, our approach operates on rich semantic structures of evidence obtained by semantic role labeling.We propose two mechanisms to exploit the structure of evidence while leveraging the advances of pre-trained models like BERT, GPT or XLNet.Specifically, using XLNet as the backbone, we first utilize the graph structure to re-define the relative distances of words, with the intuition that semantically related words should have short distances.Then, we adopt graph convolutional network and graph attention network to propagate and aggregate information from neighboring nodes on the graph.We evaluate our system on FEVER, a benchmark dataset for fact checking, and find that rich structural information is helpful and both our graph-based mechanisms improve the accuracy.Our model is the state-of-the-art system in terms of both official evaluation metrics, namely claim verification accuracy and FEVER score.

This paper presents our study of cloze-style reading comprehension by imitating human reading comprehension, which normally involves tactical comparing and reasoning over candidates while choosing the best answer. We propose a multi-choice relational reasoning (McR2) model with an aim to enable relational reasoning on candidates based on fusion representations of document, query and candidates. For the fusion representations, we develop an efficient encoding architecture by integrating the schemes of bidirectional attention flow, self-attention and document-gated query reading. Then, comparing and inferring over candidates are executed by a novel relational reasoning network. We conduct extensive experiments on four datasets derived from two public corpora, Children’s Book Test and Who DiD What, to verify the validity and advantages of our model. The results show that it outperforms all baseline models significantly on the four benchmark datasets. The effectiveness of its key components is also validated by an ablation study.

User identity linkage across social networks is an essential problem for cross-network data mining. Since network structure, profile and content information describe different aspects of users, it is critical to learn effective user representations that integrate heterogeneous information. This paper proposes a novel framework with INformation FUsion and Neighborhood Enhancement (INFUNE) for user identity linkage. The information fusion component adopts a group of encoders and decoders to fuse heterogeneous information and generate discriminative node embeddings for preliminary matching. Then, these embeddings are fed to the neighborhood enhancement component, a novel graph neural network, to produce adaptive neighborhood embeddings that reflect the overlapping degree of neighborhoods of varying candidate user pairs. The importance of node embeddings and neighborhood embeddings are weighted for final prediction. The proposed method is evaluated on real-world social network data. The experimental results show that INFUNE significantly outperforms existing state-of-the-art methods.

Deepfake detection, the task of automatically discriminating machine-generated text, is increasingly critical with recent advances in natural language generative models.Existing approaches to deepfake detection typically represent documents with coarse-grained representations.However, they struggle to capture factual structures of documents, which is a discriminative factor between machinegenerated and human-written text according to our statistical analysis.To address this, we propose a graph-based model that utilizes the factual structure of a document for deepfake detection of text.Our approach represents the factual structure of a given document as an entity graph, which is further utilized to learn sentence representations with a graph neural network.Sentence representations are then composed to a document representation for making predictions, where consistent relations between neighboring sentences are sequentially modeled.Results of experiments on two public deepfake datasets show that our approach significantly improves strong base models built with RoBERTa.Model analysis further indicates that our model can distinguish the difference in the factual structure between machine-generated text and humanwritten text.

An airline crew rostering problem (ACRP) is one of the most important problems in an airline planning process. It aims at determining an optimal assignment of pairings, which refer to sequences of flights starting from and ending at the same crew base, to aircrew to form roster lines. In practice, ACRP is subject to various types of constraints. We present a constraint-implicit mathematical model taking into account the basic, horizontal, and vertical constraints. In order to solve a kind of ACRP, we propose a construction-based variable neighborhood search (VNS) framework that can build rosters effectively. Three construction methods, i.e., crew-by-crew, pairing-by-pairing, and orthogonal constructions, are introduced. To evaluate our approaches, we conduct extensive experiments on two scenarios (intense and light workload) of instances originated from a Chinese airline company and make comparisons among different VNS approaches. The computational results show that the proposed approaches are capable of producing high-quality solutions in both scenarios.

In this paper, a novel algorithm called bi-objective elite differential evolution (BOEDE) is proposed to optimize multivalued logic (MVL) networks. It is a multiobjective algorithm completely different from all previous single-objective optimization ones. The two objective functions, error and optimality, are put into evaluating the fitness of individuals in evolution simultaneously. BOEDE innovatively uses an archive population with different ranks to store elite individuals and offsprings. Moreover, a characteristic updating method based on this archive structure is designed to produce the parent population. Because of the particularity of MVL network problems, the performance of BOEDE to solve them is further improved by strictly distinguishing elite solutions and Pareto optimal solutions, and by modifying the method of dealing with illegal variables. The simulations show that BOEDE can collect a great number of solutions to provide decision support for a variety of applications. The comparison results also indicate that BOEDE is significantly better than the existing algorithms.

Two-echelon vehicle routing problem (2E-VRP) is a challenging problem that involves both the strategic and tactical planning decisions on both echelons. The satellite locations and the customer distribution affect the cost of different components on the second echelon, thus the possibilities of satellite-to-customer assignment complicates the problem. In this paper, we propose a graph-based fuzzy evolutionary algorithm for solving 2E-VRP. The proposed method integrates a graph-based fuzzy assignment scheme into an iteratively evolutionary learning process to minimize the total cost. To resolve the possibilities of the satellite-to-customer assignment, graph-based fuzzy operator is used to take advantage of population evolution and avoid excessive fitness evaluations of unpromising moves in different satellites. Each offspring is produced via graph-based fuzzy assignment procedure out of an assignment graph from parent individuals, and fuzzy local search procedure is used to further improve the offspring. The experimental results on the public test sets demonstrate the competitiveness of the proposed method.

Periodic vehicle routing problem with time windows (PVRPTWs) is an important combinatorial optimization problem that can be applied in different fields. It is essentially a multiobjective optimization problem due to the problem nature. In this paper, a typical multiobjective PVRPTW with five objectives is first defined and new nonsymmetric real-world multiobjective PVRPTW instances are generated. Then, a hybrid multiobjective memetic algorithm is proposed for solving multiobjective PVRPTW. In the proposed algorithm, a two-phase strategy is devised to improve the comprehensive performance in terms of the convergence and diversity. In this strategy, several extreme solutions near an approximate Pareto front (PF) are identified at Phase I, and then the approximate PF is extended at Phase II. The proposed algorithm is extensively tested on both real-world instances and traditional instances. Experiment results show that the proposed algorithm outperforms two representative competitor algorithms on most of the instances. The effectiveness of the two-phase strategy is also confirmed.

It is generally accepted that the essential goal of many-objective optimization is the balance between convergence and diversity. For constrained many-objective optimization problems (CMaOPs), the feasibility of solutions should be considered as well. Then the real challenge of constrained many-objective optimization can be generalized to the balance among convergence, diversity, and feasibility. In this paper, a tri-goal evolution framework is proposed for CMaOPs. The proposed framework carefully designs two indicators for convergence and diversity, respectively, and converts the constraints into the third indicator for feasibility. Since the essential goal of constrained many-objective optimization is to balance convergence, diversity, and feasibility, the philosophy of the proposed framework matches the essential goal of constrained many-objective optimization well. Thus, it is natural to use the proposed framework to deal with CMaOPs. Further, the proposed framework is conceptually simple and easy to instantiate for constrained many-objective optimization. A variety of balance schemes and ranking methods can be used to achieve the balance among convergence, diversity and feasibility. Three typical instantiations of the proposed framework are then designed. Experimental results on a constrained many-objective optimization test suite show that the proposed framework is highly competitive with existing state-of-the-art constrained many-objective evolutionary algorithms for CMaOPs.

Mobile sequential recommendation was originally designed to find a promising route for a single taxicab. Directly applying it for multiple taxicabs may cause an excessive overlap of recommended routes. The multi-taxicab recommendation problem is challenging and has been less studied. In this paper, we first formalize a collective mobile sequential recommendation problem based on a classic mathematical model, which characterizes time-varying influence among competing taxicabs. Next, we propose a new evaluation metric for a collection of taxicab routes aimed to minimize the sum of potential travel time. We then develop an efficient algorithm to calculate the metric and design a greedy recommendation method to approximate the solution. Finally, numerical experiments show the superiority of our methods. In trace-driven simulation, the set of routes recommended by our method significantly outperforms those obtained by conventional methods.

This paper introduce a novel Position-aware Transformation Network (PTNet) for aspect-level sentiment classification. On the one hand, attention mechanisms have been employed to model the relationship between aspect and context. However, the position information of aspect words is rarely emphasized for sentiment prediction. The truth is that we should pay more attention to the word which is close to the aspect, since the words with closer distance may have a greater impact on the sentiment polarity of a sentence toward the aspect. On the other hand, existing approaches often adopt the average of aspect vectors or context vectors to calculate the attention weights, which may cause information loss if the aspect and context is not a single word. Therefore, this paper propose a position-aware layer and a context transformation layer in our model to solve the above two issues respectively. Moreover, several convolution kernels are also used to extract the n-gram information for prediction. We examine the performance of our model on three datasets: the first two are from SemEval2014 including the reviews of restaurants and laptops, and the third is a tweet collection. Experimental results show that our model consistently outperforms the state-of-the-art methods on all three datasets.

This paper presents a cooperative differential evolution framework (CCMODE) for constrained multiobjective optimization, and two instantiations of the CCMODE framework are implemented. The proposed framework has (M+1) populations, including M subpopulations for constrained single-objective optimization and an archive population for constrained M -objective optimization. Each subpopulation performs its own constrained single-objective differential evolution to optimize the assigned constrained single-objective optimization problem. For the archive population, the constraint handling techniques (CHTs) are modified for constrained multiobjective optimization. The proposed framework takes the advantage of existing effective constrained single-objective optimization algorithms, and extends them to deal with constrained multiobjective optimization problems. In two instantiations, two CHTs are implemented in CCMODE framework, respectively. Experiment results on several sets of benchmark problems with two, three, and many objectives show that the proposed algorithm is better than existing state-of-the-art constrained multiobjective evolutionary algorithms. The effectiveness of the subpopulations is also discussed.

This paper proposes a multiobjective multidepot vehicle routing problem with time windows and designs some real-world test instances. It develops a two-stage multiobjective evolutionary algorithm (TS-MOEA) for dealing with the problem. Stage I of our proposed algorithm focuses on finding extreme solutions, and forms a coarse Pareto front, while stage II extends the found extreme solutions for approximating the whole Pareto front. The two-stage strategy provides a new method to balance convergence and diversity. Moreover, a hybrid neighborhood structure is designed for solution improvement. Experimental result shows that TS-MOEA significantly outperforms two other representative algorithms.

In decomposition-based multiobjective evolutionary algorithms, the setting of search directions (or weight vectors), and the choice of reference points (i.e., the ideal point or the nadir point) in scalarizing functions, are of great importance to the performance of the algorithms. This paper proposes a new decomposition-based many-objective optimizer by simultaneously using adaptive search directions and two reference points. For each parent, binary search directions are constructed by using its objective vector and the two reference points. Each individual is simultaneously evaluated on two fitness functions-which are motivated by scalar projections-that are deduced to be the differences between two penalty-based boundary intersection (PBI) functions, and two inverted PBI functions, respectively. Solutions with the best value on each fitness function are emphasized. Moreover, an angle-based elimination procedure is adopted to select diversified solutions for the next generation. The use of adaptive search directions aims at effectively handling problems with irregular Pareto-optimal fronts, and the philosophy of using the ideal and nadir points simultaneously is to take advantages of the complementary effects of the two points when handling problems with either concave or convex fronts. The performance of the proposed algorithm is compared with seven state-of-the-art multi-/many-objective evolutionary algorithms on 32 test problems with up to 15 objectives. It is shown by the experimental results that the proposed algorithm is flexible when handling problems with different types of Pareto-optimal fronts, obtaining promising results regarding both the quality of the returned solution set and the efficiency of the new algorithm.

An artificial neural network (ANN) that mimics the information processing mechanisms and procedures of neurons in human brains has achieved a great success in many fields, e.g., classification, prediction, and control. However, traditional ANNs suffer from many problems, such as the hard understanding problem, the slow and difficult training problems, and the difficulty to scale them up. These problems motivate us to develop a new dendritic neuron model (DNM) by considering the nonlinearity of synapses, not only for a better understanding of a biological neuronal system, but also for providing a more useful method for solving practical problems. To achieve its better performance for solving problems, six learning algorithms including biogeography-based optimization, particle swarm optimization, genetic algorithm, ant colony optimization, evolutionary strategy, and population-based incremental learning are for the first time used to train it. The best combination of its user-defined parameters has been systemically investigated by using the Taguchi's experimental design method. The experiments on 14 different problems involving classification, approximation, and prediction are conducted by using a multilayer perceptron and the proposed DNM. The results suggest that the proposed learning algorithms are effective and promising for training DNM and thus make DNM more powerful in solving classification, approximation, and prediction problems.

The quay crane scheduling problem (QCSP) is one of the most important problems for the operations at container ports. The QCSP aims to decide a QC schedule for loading and unloading containers so as to minimize the vessel turnaround time. The QCSP is subject to various kinds of constraints, e.g., task precedence constraints and QC noninterference constraints. This paper extends the QCSP by taking into consideration the stability constraints, which are crucial for the safety reason but often omitted in the existing literature. We provide a mathematical model for the QCSP with stability constraints (QCSPSCs). A bicriteria evolutionary algorithm is proposed to solve the QCSPSC. The algorithm consists of a sliding-window heuristic to fix the schedule, which violates the stability constraints. Extensive experiments are conducted to demonstrate the effectiveness of the algorithm. The computational results of the traditional QCSP and the QCSPSC are also compared and analyzed.

This paper investigates a practical variant of the vehicle routing problem (VRP), called VRP with simultaneous delivery and pickup and time windows (VRPSDPTW), in the logistics industry. VRPSDPTW is an important logistics problem in closed-loop supply chain network optimization. VRPSDPTW exhibits multiobjective properties in real-world applications. In this paper, a general multiobjective VRPSDPTW (MO-VRPSDPTW) with five objectives is first defined, and then a set of MO-VRPSDPTW instances based on data from the real-world are introduced. These instances represent more realistic multiobjective nature and more challenging MO-VRPSDPTW cases. Finally, two algorithms, multiobjective local search (MOLS) and multiobjective memetic algorithm (MOMA), are designed, implemented and compared for solving MO-VRPSDPTW. The simulation results on the proposed real-world instances and traditional instances show that MOLS outperforms MOMA in most of instances. However, the superiority of MOLS over MOMA in real-world instances is not so obvious as in traditional instances.

This paper presents a cooperative differential evolution (DE) with multiple populations for multiobjective optimization. The proposed algorithm has M single-objective optimization subpopulations and an archive population for an M -objective optimization problem. An adaptive DE is applied to each subpopulation to optimize the corresponding objective of the multiobjective optimization problem (MOP). The archive population is also optimized by an adaptive DE. The archive population is used not only to maintain all nondominated solutions found so far but also to guide each subpopulation to search along the whole Pareto front. These (M+1) populations cooperate to optimize all objectives of the MOP by using adaptive DEs. Simulation results on benchmark problems with two, three, and many objectives show that the proposed algorithm is better than some state-of-the-art multiobjective DE algorithms and other popular multiobjective evolutionary algorithms. The online search behavior and parameter sensitivity of the proposed algorithm are also investigated.

Differential evolution (DE) is a simple and powerful population-based evolutionary algorithm. The salient feature of DE lies in its mutation mechanism. Generally, the parents in the mutation operator of DE are randomly selected from the population. Hence, all vectors are equally likely to be selected as parents without selective pressure at all. Additionally, the diversity information is always ignored. In order to fully exploit the fitness and diversity information of the population, this paper presents a DE framework with multiobjective sorting-based mutation operator. In the proposed mutation operator, individuals in the current population are firstly sorted according to their fitness and diversity contribution by nondominated sorting. Then parents in the mutation operators are proportionally selected according to their rankings based on fitness and diversity, thus, the promising individuals with better fitness and diversity have more opportunity to be selected as parents. Since fitness and diversity information is simultaneously considered for parent selection, a good balance between exploration and exploitation can be achieved. The proposed operator is applied to original DE algorithms, as well as several advanced DE variants. Experimental results on 48 benchmark functions and 12 real-world application problems show that the proposed operator is an effective approach to enhance the performance of most DE algorithms studied.

Differential evolution (DE) is a simple and powerful population-based evolutionary algorithm, successfully used in various scientific and engineering fields. Although DE has been studied by many researchers, the neighborhood and direction information is not fully and simultaneously exploited in the designing of DE. In order to alleviate this drawback and enhance the performance of DE, we first introduce two novel operators, namely, the neighbor guided selection scheme for parents involved in mutation and the direction induced mutation strategy, to fully exploit the neighborhood and direction information of the population, respectively. By synergizing these two operators, a simple and effective DE framework, which is referred to as the neighborhood and direction information based DE (NDi-DE), is then proposed for enhancing the performance of DE. This way, NDi-DE not only utilizes the information of neighboring individuals to exploit the regions of minima and accelerate convergence but also incorporates the direction information to prevent an individual from entering an undesired region and move to a promising area. Consequently, a good balance between exploration and exploitation can be achieved. In order to test the effectiveness of NDi-DE, the proposed framework is applied to the original DE algorithms, as well as several state-of-the-art DE variants. Experimental results show that NDi-DE is an effective framework to enhance the performance of most of the DE algorithms studied.

This paper presents a discrete competitive Hopfield neural network (HNN) (DCHNN) based on the estimation of distribution algorithm (EDA) for the maximum diversity problem. In order to overcome the local minimum problem of DCHNN, the idea of EDA is combined with DCHNN. Once the network is trapped in local minima, the perturbation based on EDA can generate a new starting point for DCHNN for further search. It is expected that the further search is guided to a promising area by the probability model. Thus, the proposed algorithm can escape from local minima and further search better results. The proposed algorithm is tested on 120 benchmark problems with the size ranging from 100 to 5000. Simulation results show that the proposed algorithm is better than the other improved DCHNN such as multistart DCHNN and DCHNN with random flips and is better than or competitive with metaheuristic algorithms such as tabu-search-based algorithms and greedy randomized adaptive search procedure algorithms.

Particle swarm optimization (PSO) is a population-based swarm intelligence algorithm. A quantum-behaved particle swarm optimization (QPSO) is also proposed by combining the classical PSO philosophy and quantum mechanics. These algorithms have been very successful in solving the global continuous optimization, but their applications to combinatorial optimization have been rather limited. Estimation of distribution algorithm (EDA) samples new solutions from a probability model which characterizes the distribution of promising solutions. This paper proposes a novel discrete QPSO based on EDA for the combinatorial optimization problem. The proposed algorithm combines global statistical information extracted by EDA with local information obtained by discrete QPSO to create promising solutions. To demonstrate the performance of the proposed algorithm, experiments are carried out on the unconstrained binary quadratic programming problem which numerous hard combinatorial optimization problems can be formulated as. The results show that the discrete QPSO based on EDA have superior performance to other algorithms.

Recently, a special kind of recurrent neural networks has been proposed by Zhang et al for online solution of Sylvester equation with time-varying coefficients. Their neural dynamics are elegantly introduced by defining a matrix-valued error function rather than the usual scalar-valued norm-based error function, so that the computational error can vanish to zero globally and exponentially. The resultant Zhang neural networks (ZNN), perform much better on solving time-varying problems in comparison with gradient-based neural networks. MATLAB Simulink is a software package for model-based design and multi-domain simulation of dynamic systems. By using click-and-drag mouse operations, it is much easier to model and simulate complex neural systems as compared to MATLAB coding. This paper investigates the MATLAB Simulink modeling and simulative verification of ZNN models for timevarying Sylvester equation solving. Computer-simulation results substantiate the ZNN efficacy on solving online the time-varying problems (specifically, the time-varying Sylvester equation).

In this paper, a framework of hybrid PSO is proposed by reasonablycombining the Q-bit evolutionary search of quantum PSO and binary bit evolutionary search of genetic PSO.

In this paper, introducing stochastic dynamics into an optimal competitive Hopfield network model (OCHOM), we propose a new algorithm that permits temporary energy increases which helps the OCHOM escape from local minima. The goal of the maximum cut problem, which is an NP-complete problem, is to partition the node set of an undirected graph into two parts in order to maximize the cardinality of the set of edges cut by the partition. The problem has many important applications including the design of VLSI circuits and design of communication networks. Recently, Galán-Marín et al. proposed the OCHOM, which can guarantee convergence to a global/local minimum of the energy function, and performs better than the other competitive neural approaches. However, the OCHOM has no mechanism to escape from local minima. The proposed algorithm introduces stochastic dynamics which helps the OCHOM escape from local minima, and it is applied to the maximum cut problem. A number of instances have been simulated to verify the proposed algorithm.

In this paper, based on maximum neural network, we propose a new parallel algorithm that can help the maximum neural network escape from local minima by including a transient chaotic neurodynamics for bipartite subgraph problem. The goal of the bipartite subgraph problem, which is an NP- complete problem, is to remove the minimum number of edges in a given graph such that the remaining graph is a bipartite graph. Lee et al. presented a parallel algorithm using the maximum neural model (winner-take-all neuron model) for this NP- complete problem. The maximum neural model always guarantees a valid solution and greatly reduces the search space without a burden on the parameter-tuning. However, the model has a tendency to converge to a local minimum easily because it is based on the steepest descent method. By adding a negative self-feedback to the maximum neural network, we proposed a new parallel algorithm that introduces richer and more flexible chaotic dynamics and can prevent the network from getting stuck at local minima. After the chaotic dynamics vanishes, the proposed algorithm is then fundamentally reined by the gradient descent dynamics and usually converges to a stable equilibrium point. The proposed algorithm has the advantages of both the maximum neural network and the chaotic neurodynamics. A large number of instances have been simulated to verify the proposed algorithm. The simulation results show that our algorithm finds the optimum or near-optimum solution for the bipartite subgraph problem superior to that of the best existing parallel algorithms.

By analyzing the dynamic behaviors of the transiently chaotic neural network and greedy heuristic for the maximum independent set (MIS) problem, we present an improved transiently chaotic neural network for the MIS problem in this paper. Extensive simulations are performed and the results show that this proposed transiently chaotic neural network can yield better solutions to p-random graphs than other existing algorithms. The efficiency of the new model is also confirmed by the results on the complement graphs of some DIMACS clique instances in the second DIMACS challenge. Moreover, the improved model uses fewer steps to converge to stable state in comparison with the original transiently chaotic neural network.