The use of digital microfluidic biochips (DMFBs) has highlighted their superiority in automatically executing biochemical assays by controlling tiny nano/picoliter droplets, which are moved in parallel to enhance throughput. Routing-based synthesis for DMFBs yields faster assay execution times compared to module-based synthesis when on-chip resource constraints are stringent. However, without predefining modules, it is very challenging to handle all the droplets directly on the chip for successfully executing the desired biochemical assay, especially in dynamic environments. Through modeling routing-based synthesis into two kinds of real-time decision tasks, i.e., transportation and mixing, this paper proposes a new routing-based synthesis framework that uses deep reinforcement learning (DRL) to train transportation and mixing agents respectively. Additionally, we design effective partial observations and curriculum learning (CL) schemes for both kinds of agents to improve their generalization ability and accelerate the training process. Compared to the state-of-the-art heuristic routing-based synthesis methods, more efficient synthesis processes of the given assays can be achieved using the proposed method of combining DRL and CL. For example, the average completion time on several real-world bioassay benchmarks (PCR, INVITRO, and PROTEIN) was reduced by 12.9% 18.5% approximately.

The generation of motion behaviors plays a pivotal role in constructing effective simulated scenarios for testing autonomous driving systems (ADSs). The controllability (i.e., the ability to synthesize specific motion patterns) and multimodality (i.e., the capacity to represent multiple motion intentions) of generated motion behaviors are essential for the purposeful and comprehensive evaluation of ADS. Although recent studies have made progress in either multimodal or controllable motion behavior generation, it remains a major challenge to simultaneously generate multimodal motion behaviors in a controllable manner. In this work, we propose a unified framework, CoMoGen, to generate multimodal motion behaviors in a controllable manner under open-loop evaluation assumption. The proposed framework consists of three core components: i) a learning-based vehicle placer, responsible for positioning generated vehicles in non-conflicting initial locations; ii) a robust model-based trajectory candidate generator, capable of synthesizing controllable and multimodal trajectory candidates. iii) a learning-based trajectory selector, developed to evaluate and select multimodal trajectories for the placed vehicles. Experiments on the INTERACTION dataset demonstrate strong controllability and multimodality of CoMoGen. Further experiments on three additional real-world datasets, that are unseen during training, as well as on diverse synthesized high-definition maps, validate the remarkable generalization capability of CoMoGen.

Inadequate consideration of tactile sensor features in existing algorithms can lead to insufficient prediction accuracy for robotic tactile recognition tasks. In this paper, we propose a spatial-temporal information based adjacency matrix construction method called transfer cost. On this basis, we propose a multi-branch multi-scale channel fusion graph convolutional network (MSCF-LSTM-GCN). This network combines the advantages of long short-term memory networks (LSTM) with graph convolutional networks (GCN) to extract spatial-temporal features. It is the first LSTM-GCN network with a multi-branch structure that utilizes multi-feature scale and multi-channel fusion. This structure provides diverse perceptual ranges and information levels. We introduce shortcuts combined with the multi-branch structure to reduce the loss of information caused by multiple layers of transmission. The Einstein summation calculation method and the parameters of binarizing the adjacency matrix are optimized to enable the established dynamic tactile graph to participate in batch training. The proposed method improves both prediction accuracy and F1 score by over 1% on the tactile grasp stability prediction task. In the tactile object recognition task, the proposed method improves both prediction accuracy and F1 score by over 3%.Note to Practitioners—Robotic tactile perception is an important research area that can improve the flexibility, accuracy and stability of robots in robotic tactile recognition tasks. However, the amount of accessible information depends on the resolution and number of tactile sensors, and the features extracted using conventional deep learning methods are limited. For this reason, we propose a spatial-temporal information based adjacency matrix construction method called transfer cost. Then, we propose the MSCF-LSTM-GCN model that extract spatial-temporal features from different feature scales and shortcuts. The network solves the problems of traditional deep learning methods in acquiringsingle features and losing deep information. The experiments on two public datasets show that our method performs due to other competing algorithms on the tasks of robotic grasp stability prediction and object recognition for multi-tactile sensor scenarios. In future research we will invest in the problem of 3D force regression.

This paper comprehensively reviews the metrics for measuring the diversity of game scenarios, spotlighting the innovative use of procedural content generation and other fields as cornerstones for enriching player experiences through diverse game scenarios. By traversing a wide array of disciplines, from affective modeling and multiagent systems to psychological studies, our research underscores the importance of diverse game scenarios in gameplay and education. Through a taxonomy of diversity metrics and evaluation methods, we aim to bridge the current gaps in literature and practice, offering insights into effective strategies for measuring and integrating diversity in game scenarios. Our analysis highlights the necessity for a unified taxonomy to aid developers and researchers in crafting more engaging and varied game worlds. This survey not only charts a path for future research in diverse game scenarios but also serves as a handbook for industry practitioners seeking to leverage diversity as a key component of game design and development.

Dynamic material handling (DMH) involves the assignment of dynamically arriving material transporting tasks to suitable vehicles in real time for minimizing makespan and tardiness. In real-world scenarios, historical task records are usually available, which enables the training of a decision policy on multiple instances consisting of historical records. Recently, reinforcement learning (RL) has been applied to solve DMH. Due to the occurrence of dynamic events such as new tasks, adaptability is highly required. Solving DMH is challenging since constraints, including task delay, should be satisfied. A feedback is received only when all tasks are served, which leads to sparse reward. Besides, making the best use of limited computational resources and historical records for training a robust policy is crucial. The time allocated to different problem instances would highly impact the learning process. To tackle those challenges, this article proposes a novel adaptive constrained evolutionary RL (ACERL) approach, which maintains a population of actors for diverse exploration. ACERL accesses each actor for tackling sparse rewards and constraint violation to restrict the behavior of the policy. Moreover, ACERL adaptively selects the most beneficial training instances for improving the policy. Extensive experiments on eight training and eight unseen test instances demonstrate the outstanding performance of ACERL compared with several state-of-the-art algorithms. Policies trained by ACERL can schedule the vehicles while fully satisfying the constraints. Additional experiments on 40 unseen noised instances show the robust performance of ACERL. Cross validation further presents the overall effectiveness of ACREL. Besides, a rigorous ablation study highlights the coordination and benefits of each ingredient of ACERL.

In non-stationary data streams, the challenges of concept drift are further compounded by the issue of Intermediate Verification Latency (IVL), which can impede timely model adaptation. IVL refers to the finite delay between the arrival of data features and their corresponding labels. This delay could pose a significant challenge in adapting models to new concepts, ultimately hindering predictive performance. However, existing IVL approaches exhibit certain limitations. Some approaches passively wait for delayed labels, thereby overlooking temporarily unlabeled data. Other approaches employ pseudo-labeling for immediate model updates, but may risk losing valuable information when reverting model states to rectify previous pseudo-labeling mistakes. To overcome these limitations, we propose a novel approach called Micro-cluster based Immediate Pseudo-Labeling with Oriented Synthetic Correction (MIPLOSC). MIPLOSC leverages micro-cluster systems to effectively capture data distributions, thus facilitating its two core components: immediate pseudo-labeling and oriented synthetic correction. The immediate pseudo-labeling mechanism facilitates immediate utilization of temporarily unlabeled data, and the oriented synthetic correction mechanism enables finergrained rectification from previous erroneous pseudo-labels and concept drift, minimizing the loss of learned information. Experimental studies validated the effectiveness of MIPLOSC in addressing IVL, demonstrating its superiority over competing methods in both space consumption and predictive performance across varying degrees of label delay.

With growing concerns about the unwanted bias or discrimination in machine learning, a number of fairness-aware machine learning algorithms have been developed to mitigate bias in the prediction. Because the objectives of accuracy and fairness are antagonistic, it is hard to balance the trade-off between them. Recently, Multi-objective Evolutionary Learning (MOEL) framework has been proposed to train a set of Pareto models with the consideration of accuracy and fairness simultaneously. However, this framework prefers to train more accurate models rather than fairer models due to the lack of gradient in terms of fairness. In this paper, MOEL is enhanced through introducing Adversarial Learning (AL). The MOEL-AL framework aims to maximize a set of predictors' ability to predict true labels and minimize the ability of an adversarial network to predict the sensitive attributes from the predictors' output. Specifically, the adversarial network can be regarded as a proxy of the undifferentiable fairness metrics, so it is possible to propagate gradients in terms of both accuracy and fairness for the predictors during the back-propagation process. Besides, the adversarial strength for different predictors is adjusted dynamically according to their fairness metric. Compared with the state-of-the-art methods, experimental studies on seven well-known datasets show that our method can provide a set of fairer Pareto models with little drop on accuracy.

Memristive crossbar-based architecture provides an energy-efficient platform to accelerate neural networks (NNs) thanks to its Processing-in-Memory (PIM) nature. However, the device-to-device variation (DDV), which is typically modeled as Lognormal distribution, deviates the programmed weights from their target values, resulting in significant performance degradation. This paper proposes a new Bayesian Neural Network (BNN) approach to enhance the robustness of weights against DDV. Instead of using the widely-used Gaussian variational posterior in conventional BNNs, our approach adopts a DDV-specific variational posterior distribution, i.e., Lognormal distribution. Accordingly, in the new BNN approach, the prior distribution is modified to keep consistent with the posterior distribution to avoid expensive Monte Carlo simulations. Furthermore, the mean of the prior distribution is dynamically adjusted in accordance with the mean of the Lognormal variational posterior distribution for better convergence and accuracy. Compared with the state-of-the-art approaches, experimental results show that the proposed new BNN approach can significantly boost the inference accuracy with the consideration of DDV on several well-known datasets and modern NN architectures. For example, the inference accuracy can be improved from 18% to 74% in the scenario of ResNet-18 on CIFAR-10 even under large variations.

In recent years, memristive crossbar-based neuromorphic computing systems (NCS) have provided a promising solution to the acceleration of neural networks. However, stuck-at faults (SAFs) in the memristor devices significantly degrade the computing accuracy of NCS. Besides, the memristor suffers from the process variations, causing deviation of the actual programming resistance from its target resistance. In this paper, we propose a reliability-driven design framework for a memristive crossbar-based NCS in combination with general and chip-specific design optimizations. First, we design a general reliability-aware training scheme to enhance the robustness of NCS to SAFs and device variations; a dropconnect-inspired approach is developed to alleviate the impact of SAFs; a new weighted error function, including cross-entropy error (CEE), the$l_{2}$-norm of weights, and the sum of squares of first-order derivatives of CEE with respect to weights, is proposed to obtain a smooth error curve, where the effects of variations are suppressed. Second, given the neural network model generated by the reliability-aware training scheme, we exploit chip-specific mapping and re- training to further improve computation accuracy loss incurred by SAFs. Experimental results show that the proposed method can boost the computation accuracy of NCS and improve the NCS robustness. Note to Practitioners—This work is motivated by the manufacturing reliability problem in a memristive crossbar-based NCS. To enhance the robustness of an NCS to SAFs and device variations, this paper presents a reliability-driven design framework with taking account of both general and chip-specific design optimizations. The experimental results have demonstrated that the proposed framework is superior to the prior arts, and can be easily integrated with existing industrial hardware-based fault tolerance solutions for higher accuracy at lower overhead. Memristive crossbar-based computing system gives hope for the anticipated efficient implementation of artificial neuromorphic networks. With the help of the reliability-driven designs, the computation accuracy is restored, and hence we can expect the wide use of memristive crossbar-based computing system in neuromorphic computing applications.

Digital microfluidic biochips (DMFBs) have shown great advantages in automatically executing biochemical protocols through manipulating discrete nano/picoliter droplets which are transported in parallel to achieve high-throughput outcomes. However, because of electrode degradations, the droplet transportation may fail, causing incorrect fluidic operations. To perform safety-critical bio-protocols, the reliability of droplet transportation becomes an utmost concern for DMFBs. It has been shown by the previous works that a reliable transportation policy can be learned using reinforcement learning (RL)-based methods by capturing the underlying health conditions of electrodes and making online decisions. However, previous RL methods may fail to accomplish routing tasks with multiple droplets, because there is a lack of cooperation among different agents (each agent represents one droplet). To deal with this problem and scale RL methods to many droplets, this article proposes a new cooperative centralized learning and distributed execution multiagent RL (MARL) framework for droplet routing in DMFBs using value-decomposition networks (VDNs). Moreover, to speed up the training and decision process as well as apply our method in large biochips, we use a partial observation space where agents can only observe environment in a limited field of view (FOV) centered around themselves. Compared with the state-of-the-art approach, the superior performance of the proposed approach is demonstrated on different DMFBs in terms of success rate and average completion time. We also validate our method on large biochips (e.g.,$\mathbf {50\times 50}$DMFBs) with more droplets than state-of-the-art approach (e.g., ten droplets).

Dynamic time-linkage optimization problems (DTPs) are special dynamic optimization problems (DOPs) with the time-linkage property. The environment of DTPs changes not only over time but also depends on the previous applied solutions. DTPs are hardly solved by existing dynamic evolutionary algorithms because they ignore the time-linkage property. In fact, they can be viewed as multiple decision-making problems and solved by reinforcement learning (RL). However, only some discrete DTPs are solved by RL-based evolutionary optimization algorithms with the assumption of observable objective functions. In this work, we propose a dynamic evolutionary optimization algorithm using surrogate-assisted$Q$-learning for continuous black-box DTPs. To observe the states of black-box DTPs, the state extraction and prediction methods are applied after the search process at each time step. Based on the learned information, a surrogate-assisted$Q$-learning is introduced to evaluate and select candidate solutions in the continuous decision space in a long-term consideration. We evaluate the components of our proposed algorithm on various benchmark problems to study their behaviors. Results of comparative experiments indicate that the proposed algorithm outperforms other compared algorithms and performs robustly on DTPs with up to 30 decision variables and different dynamic changes.

Electronic design automation (EDA) comprises a series of computationally difficult optimization problems that require substantial specialized knowledge as well as a considerable amount of trial-and-error efforts. However, open challenges, including long simulation runtime and lack of generalization, continue to restrict the applications of the existing EDA tools. Recently, learning-based algorithms, especially reinforcement learning (RL), have been successfully applied to handle various combinatorial optimization problems by automatically acquiring knowledge from the past experience. In this article, we formulate the floorplanning problem, the first stage of the physical design flow, as a Markov decision process (MDP). An end-to-end learning-based floorplanning framework GoodFloorplan is proposed to explore the design space, which combines graph convolutional network (GCN) and RL. Experimental results demonstrate that compared with state-of-the-art heuristic-based floorplanners, the proposed GoodFloorplan can provide better area and wirelength.

Some signal processing and multimedia applications can be specified by synchronous dataflow (SDF) models. The problem of SDF mapping to a given set of heterogeneous processors has been known to be NP-hard and widely studied in the design automation field. However, modern embedded applications are becoming increasingly complex with dynamic behaviors changes over time. As a significant extension to the SDF, the multi-mode dataflow (MMDF) model has been proposed to specify such an application with a finite number of behaviors (or modes) and each behavior (mode) is represented by an SDF graph. The multiprocessor mapping of an MMDF is far more challenging as the design space increases with the number of modes. Instead of using traditional genetic algorithm (GA)-based design space exploration (DSE) method that encodes the design space as a whole, this article proposes a novel cooperative co-evolutionary genetic algorithm (CCGA)-based framework to efficiently explore the design space by a new problem-specific decomposition strategy in which the solutions of node mapping for each individual mode are assigned to an individual population. Besides, a problem-specific local search operator is introduced as a supplement to the global search of CCGA for further improving the search efficiency of the whole framework. Furthermore, a fitness approximation method and a hybrid fitness evaluation strategy are applied for reducing the time consumption of fitness evaluation significantly. The experimental studies demonstrate the advantage of the proposed DSE method over the previous GA-based method. The proposed method can obtain an optimization result with 2×−3× better quality using less (1/2−1/3) optimization time.

Digital microfluidic biochips (DMFBs) have been a revolutionary platform for automating and miniaturizing laboratory procedures with the advantages of flexibility and reconfigurability. The placement problem is one of the most challenging issues in the design automation of DMFBs. It contains three interacting NP-hard sub-problems: resource binding, operation scheduling, and module placement. Besides, during the optimization of placement, complex constraints must be satisfied to guarantee feasible solutions, such as precedence constraints, storage constraints, and resource constraints. In this article, a new placement method for DMFB is proposed based on an evolutionary algorithm with novel heuristic-based decoding strategies for both operation scheduling and module placement. Specifically, instead of using the previous list scheduler and path scheduler for decoding operation scheduling chromosomes, we introduce a new heuristic scheduling algorithm (called order scheduler) with fewer limitations on the search space for operation scheduling solutions. Besides, a new 3D placer that combines both scheduling and placement is proposed where the usage of the microfluidic array over time in the chip is recorded flexibly, which is able to represent more feasible solutions for module placement. Compared with the state-of-the-art placement methods (T-tree and 3D-DDM), the experimental results demonstrate the superiority of the proposed method based on several real-world bioassay benchmarks. The proposed method can find the optimal results with the minimum assay completion time for all test cases.

In recent years, memristive crossbar-based neuromorphic computing systems (NCS) have provided a promising solution to the acceleration of neural networks. However, stuck-at faults (SAFs) in the memristor devices significantly degrade the computing accuracy of NCS. Besides, the memristor suffers from the process variations, causing deviation of the actual programming resistance from its target resistance. In this paper, we propose a reliability-driven network training framework for a memristive crossbar-based NCS, with taking account of both SAFs and device variations challenges. A dropout-inspired approach is first developed to alleviate the impact of SAFs. A new weighted error function, including cross-entropy error (CEE), the l2-norm of weights, and the sum of squares of first-order derivatives of CEE with respect to weights, is further proposed to obtain a smooth error curve, where the effects of variations are suppressed. Experimental results show that the proposed method can boost the computation accuracy of NCS and improve the NCS robustness.

The rate of transient faults has increased significantly as the technology scales up. The tolerance of transient faults has become an important issue in the system design. Dual modular redundancy (DMR) and triple modular redundancy (TMR) are two commonly used techniques that can achieve fault detection and masking through executing redundant tasks. As DMR and TMR have different time and cost overheads, we must carefully determine which one should be used for each task (i.e., task hardening) to achieve the optimal system design. Furthermore, for multi-core systems, the system-level design includes the allocation of cores for the tasks (i.e., task mapping) as well. This paper aims at task hardening and mapping simultaneously for independent tasks on multi-cores with heterogeneous performances, in order to minimize the maximum completion time of all tasks (i.e., makespan). We demonstrate that once task hardening is given, task mapping of independent tasks can be achieved by employing min–max-weight perfect matching with a polynomial time complexity. Besides, as there is a trade-off between cost and time performance, we propose a multi-objective memetic algorithm (MOMA)-based task hardening method to obtain a set of solutions with different numbers of cores (i.e., costs), so the designer can choose different solutions according to different requirements. The key idea of the MOMA is to incorporate problem-specific knowledge into the global search of evolutionary algorithms. Our experimental studies have demonstrated the effectiveness of the proposed method and have shown that by combining the results of MOMA and MOEA we can provide a designer with a highly accurate set of solutions within a reasonable amount of time.

The design space exploration (DSE) of fault-tolerant multiprocessor systems is very complex, as it contains three interacting NP-hard problems: 1) task hardening; 2) task mapping; and 3) task scheduling. In addition, replication-based task hardening can introduce new tasks, called replicas, into the system, enlarging the design space further. As a population-based global optimization algorithm, evolutionary algorithms (EAs) have been widely used to explore this huge design space over the last decade. However, as analyzed in this paper, the search space of previous works is highly redundant, resulting in poor efficiency and scalability. This paper proposes an efficient EA-based DSE method for the design of large-scale fault-tolerant multiprocessor systems. The main novelties of this paper include: 1) mapping exploration is explicitly separated, i.e., task mapping is optimized during the evolutionary search, while replica mapping is constructed heuristically according to the current co-synthesis state; 2) the design space of task hardening and task mapping are explored independently by a cooperative co-EA; and 3) as a complement to global search of EA, problem-specific local search operators are designed for both task hardening and task mapping, reducing the number of fitness evaluations required. Compared with the most relevant state-of-the-art method, the superiority of the proposed method is demonstrated using extensive experiments on a large set of benchmarks, e.g., 1.75×~2.50× better results can be obtained on the benchmarks of 300 tasks and 30 processors.

The Capacitated Arc Routing Problem (CARP) is an essential and challenging problem in smart logistics. Parameter tuning is commonly encountered in designing and applying heuristic or meta-heuristic algorithms for CARP. Recently, automatic parameter tuning or hyper-parameter optimization, which focuses on automatically finding an optimal parameter setting of an algorithm for problems at hand, has attracted considerable attention and become popular for addressing parameter tuning problems. This paper studies automatic parameter tuning for advanced algorithms in solving CARP. When designing algorithms for CARP, parameters are usually determined through empirical analysis or following some rules of thumb. This paper uses an automatic parameter tuning approach, that is, Bayesian optimization method, to tune an algorithm called SAHiD, which is a scalable approach based on hierarchical decomposition for large-scale CARP. The experimental results show that the algorithm's performance can be significantly improved with automatic parameter tuning. The tuned SAHiD algorithm obtains better solutions and faster convergence speed than original SAHiD on test CARP instances.

The recently proposed Scalable Approach Based on Hierarchical Decomposition (SAHiD) has shown its superiority on large-scale capacitated arc routing problems (CARP) in terms of both computational efficiency and solution quality. The main idea of SAHiD is that the underlying Hierarchical decomposition (HD) scheme is able to efficiently obtain a good permutation of tasks for CARP in a hierarchical divide-and-conquer way, where both the number and size of subproblems can be kept in tractable for large-scale problems with thousands of tasks. Motivated by the frequent observations of the similarity between CARP and Capacitated Vehicle Routing Problem (CVRP), the HD scheme and SAHiD algorithm are expected to work well on CVRPs. This paper applies SAHiD to large-scale CVRPs and discovers that SAHiD does not work as well as expected on large-scale CVRP. Possible reasons for this are given after extensive experimental studies. Two directions for improving SAHiD on large-scale CVRP are pointed out.

A well-defined distance is critical for the performance of time series classification. Existing distance measurements can be categorized into two branches. One is to utilize handmade features for calculating distance, e.g., dynamic time warping, which is limited to exploiting the dynamic information of time series. The other methods make use of the dynamic information by approximating the time series with a generative model, e.g., Fisher kernel. However, previous distance measurements for time series seldom exploit the label information, which is helpful for classification by distance metric learning. In order to attain the benefits of the dynamic information of time series and the label information simultaneously, this paper proposes a multiobjective learning algorithm for both time series approximation and classification, termed multiobjective model-metric (MOMM) learning. In MOMM, a recurrent network is exploited as the temporal filter, based on which, a generative model is learned for each time series as a representation of that series. The models span a non-Euclidean space, where the label information is utilized to learn the distance metric. The distance between time series is then calculated as the model distance weighted by the learned metric. The network size is also optimized to learn parsimonious representations. MOMM simultaneously optimizes the data representation, the time series model separation, and the network size. The experiments show that MOMM achieves not only superior overall performance on uni/multivariate time series classification but also promising time series prediction performance.

Semi-supervised learning (SSL) concerns the problem of how to improve classifiers’ performance through making use of prior knowledge from unlabeled data. Many SSL methods have been developed to integrate unlabeled data into the classifiers based on either the manifold or cluster assumption in recent years. In particular, the graph-based approaches, following the manifold assumption, have achieved a promising performance in many real-world applications. However, most of them work well on small-scale data sets only and lack probabilistic outputs. In this paper, a scalable graph-based SSL framework through sparse Bayesian model is proposed by defining a graph-based sparse prior. Based on the traditional Bayesian inference technique, a sparse Bayesian SSL algorithm (SBS$^2$L) is obtained, which can remove the irrelevant unlabeled samples and make probabilistic prediction for out-of-sample data. Moreover, in order to scale SBS$^2$L to large-scale data sets, an incremental SBS$^2$L (ISBS$^2$L) is derived. The key idea of ISBS$^2$L is employing an incremental strategy and sequentially selecting parts of unlabeled samples that contribute to the learning instead of using all available unlabeled samples directly. ISBS$^2$L has lower time and space complexities than previous SSL algorithms with the use of all unlabeled samples. Extensive experiments on various data sets verify that our algorithms can achieve comparable classification effectiveness and efficiency with much better scalability. Finally, the generalization error bound is derived based on robustness analysis.

High defect density and extreme parameter variation make it very difficult to implement reliable logic functions in crossbar-based nanoarchitectures. It is a major design challenge to tolerate defects and variations simultaneously for such architectures. In this paper, a method based on a bipartite matching and memetic algorithm is proposed for defect- and variation-tolerant logic mapping (D/VTLM) problem in crossbar-based nanoarchitectures. In the proposed method, the search space of the D/VTLM problem can be dramatically reduced through the introduction of the min-max weight maximum-bipartite-matching (MMW-MBM) and a related heuristic bipartite matching method. MMW-MBM is defined on a weighted bipartite graph as an MBM, where the maximal weight of the edges in the matching has a minimal value. In addition, a defect- and variation-aware local search (D/VALS) operator is proposed for D/VTLM and embedded in a global search framework. The D/VALS operator is able to utilize the domain knowledge extracted from problem instances and, thus, has the potential to search the solution space more efficiently. Compared with the state-of-the-art heuristic and recursive algorithms, and a simulated annealing algorithm, the good performance of our proposed method is verified on a 3-bit adder and a large set of random benchmarks of various scales.

The maximum balanced biclique problem (MBBP), an NP-hard combinatorial optimization problem, has been attracting more attention in recent years. Existing node-deletion-based algorithms usually fail to find high-quality solutions due to their easy stagnation in local optima, especially when the scale of the problem grows large. In this paper, a new algorithm for the MBBP, evolutionary algorithm with structure mutation (EA/SM), is proposed. In the EA/SM framework, local search complemented with a repair-assisted restart process is adopted. A new mutation operator, SM, is proposed to enhance the exploration during the local search process. The SM can change the structure of solutions dynamically while keeping their size (fitness) and the feasibility unchanged. It implements a kind of large mutation in the structure space of MBBP to help the algorithm escape from local optima. An MBBP-specific local search operator is designed to improve the quality of solutions efficiently; besides, a new repair-assisted restart process is introduced, in which the Marchiori's heuristic repair is modified to repair every new solution reinitialized by an estimation of distribution algorithm (EDA)-like process. The proposed algorithm is evaluated on a large set of benchmark graphs with various scales and densities. Experimental results show that: 1) EA/SM produces significantly better results than the state-of-the-art heuristic algorithms; 2) it also outperforms a repair-based EDA and a repair-based genetic algorithm on all benchmark graphs; and 3) the advantages of EA/SM are mainly due to the introduction of the new SM operator and the new repair-assisted restart process.

Due to the super scale, high defect density, and per-chip designing paradigm of emerging nanoelectronics, the runtime of the algorithms for defect-tolerant design is of vital importance from the perspective of practicability. In this article, an efficient and effective heuristic defect-free subcrossbar extraction algorithm is proposed which improves performance by mixing the heuristics from two state-of-the-art algorithms and then is speeded up significantly by considerably reducing the number of major loops. Compared with the current most effective algorithm that improves the solution quality (i.e., size of the defect-free subcrossbar obtained) at the cost of high time complexity O ( n 3 ), the time complexity of the proposed heuristic algorithm is proved to be O ( n 2 ). Using a large set of instances of various scales and defect densities, the simulation results show that the proposed algorithm can offer similar high-quality solutions as the current most effective algorithm while consuming much shorter runtimes (reduced to about 1/3 to 1/5) than the current most effective algorithm.

The defect-tolerant logic mapping (DTLM), which has been proved to be an NP-complete combinatorial search problem, is a key step for logic implementation in emerging crossbar-based nano-architectures. However, no practically satisfactory solution has been suggested for the DTLM until now. In this paper, the problem of DTLM is first modeled as a combinatorial optimization problem through the introduction of maximum-bipartite-matching. Then, a new memetic algorithm with fitness approximation (MA/FA) is proposed to solve the optimization problem efficiently. In MA/FA, a new greedy reassignment local search operator, capable of utilizing the domain knowledge and information from problem instances, is designed to help the algorithm find optimal logic mapping with consumption of relatively lower computational resources. A fitness approximation method is adopted to reduce the time consumption of fitness evaluation dramatically. In addition, a hybrid fitness evaluation strategy that combines the exact and approximated fitness evaluation methods is presented to balance the accuracy and time efficiency of fitness evaluation. The effectiveness and efficiency of the proposed methods are testified and evaluated on a large set of benchmark instances of various scales, and the advantage of MA/FA on keeping good balance between effectiveness and efficiency is also observed.