Evolutionary algorithms are well suited to neural architecture search and other combinatorial design problems, but their scalability is often limited by the high cost of fitness evaluation. This paper studies evolutionary multi-objective optimisation in a regime where fitness evaluations are effectively free, enabled by a training-free proxy for neural network expressivity. We propose SWAP-Lite, a Pareto-guided evolutionary algorithm that maintains an explicit archive of non-dominated solutions over representational capacity and deployment cost, yielding an anytime optimiser that exposes budget-feasible solutions throughout the search. Using a MobileNet-style architecture space as a case study, we instantiate the fitness function with a sample-wise activation pattern proxy and perform large-scale evolutionary searches with up to 105 architecture evaluations. Experiments on CIFAR-10 and ImageNet show that SWAP-Lite discovers compact architectures that are competitive with state-of-the-art training-based and zero-shot baselines, while reducing search cost by one to four orders of magnitude. Analysis of the evolutionary dynamics demonstrates that explicit bi-objective optimisation produces higher-quality constrained Pareto fronts and superior anytime hypervolume compared with random search, greedy local search, and single-objective evolutionary baselines.

Zero-shot proxies, also known as training-free metrics, are widely adopted to reduce the computational overhead in neural network evaluation for scenarios such as Neural Architecture Search (NAS), as they do not require any training. Existing zero-shot metrics have several limitations, including weak correlation with the true performance and poor generalisation across different networks or downstream tasks. For example, most of these metrics apply only to either convolutional neural networks (CNNs) or Transformers, but not both. To address these limitations, we propose Sample-Wise Activation Patterns (SWAP), and its derivative, SWAP-Score, a novel and highly effective zero-shot metric. SWAP-Score is broadly applicable across both architecture families and task domains, demonstrating strong predictive performance in the majority of tasks. This metric measures the expressivity of neural networks over a mini-batch of samples, showing a high correlation with the neural networks' ground-truth performance. For both CNNs and Transformers, the SWAP-Score outperforms existing zero-shot metrics across computer vision and natural language processing tasks. For instance, Spearman's correlation coefficient between the SWAP-Score and CIFAR-10 validation accuracy for DARTS CNNs is 0.93, and 0.71 for FlexiBERT Transformers on GLUE tasks. Moreover, SWAP-Score is label-independent, hence can be applied at the pre-training stage of language models to estimate their performance for downstream tasks. When applied to NAS, SWAP-empowered NAS, SWAP-NAS can achieve competitive performance using only approximately 6 and 9 minutes of GPU time, on CIFAR-10 and ImageNet respectively.

Neural architecture search (NAS) aims to automatically design high-performance architectures of deep neural networks, which have shown great potential in various fields. However, the search process of NAS is computationally expensive since plenty of deep neural networks are trained to get the performance on GPUs. Performance predictors can directly estimate the performance of architectures without GPU-based training, thus can overcome this barrier. However, the construction of performance predictors requires labeling plenty of architectures sampled from the corresponding NAS search space, which is still prohibitively costly. In this paper, we propose a Domain Adaptive performance Predictor (DAP), which can construct a performance predictor based on the labeled architectures provided by existing benchmarks and then enable it to other search spaces via domain adaptive techniques. To achieve this, we first propose a domain-agnostic feature extraction method to refine the domain-invariant features of neural architectures. Then, we propose a novel embedding method to learn the shared representations of architecture operations. Experimental results demonstrate that DAP outperforms eight baselines upon six popular search spaces. Notably, we only require the search cost of 0:0002 GPU Days to find the architecture with 77:10% top-1 accuracy on ImageNet and 97:86% on CIFAR-10. In addition, we show the theoretical upper bound of the generalization error in the target search space, further illustrating the generalizability of DAP. The source code is available athttps://anonymous.4open.science/r/DAP-2F1F/.

Multi-objective neural architecture search (NAS) aims to find a set of model architectures to achieve different trade-offs between the model performance and the model complexity. The evaluation of the model performance usually requires a time-consuming training process, which is the main bottleneck in a NAS algorithm. To address this issue, many training-free metrics have been proposed in the literature to estimate the model performance without training. In this paper, we examine 13 training-free metrics on a two-objective NAS problem based on NAS-Bench-201. Our results show that the training-free metric which has a high correlation with the model performance does not always generate an estimated Pareto front with high quality. We embed these training-free metrics into four widely-used evolutionary multi-objective optimization algorithms (EMOAs) to solve the two-objective NAS problem. Our results show that the EMOAs with the Synaptic Flow metric obtain the best approximation of the Pareto front among the 13 training-free metrics.

Self-attention mechanism is the key of the Transformer but often criticized for its computation demands. Previous token pruning works motivate their methods from the view of computation redundancy but still need to load the full network and require same memory costs. This paper introduces a novel strategy that simplifies vision transformers and reduces computational load through the selective removal of non-essential attention layers, guided by entropy considerations. We identify that regarding the attention layer in bottom blocks, their subsequent MLP layers, i.e. two feed-forward layers, can elicit the same entropy quantity. Meanwhile, the accompanied MLPs are under-exploited since they exhibit smaller feature entropy compared to those MLPs in the top blocks. Therefore, we propose to integrate the uninformative attention layers into their subsequent counterparts by degenerating them into identical mapping, yielding only MLP in certain transformer blocks. Experimental results on ImageNet-1k show that the proposed method can remove 40% attention layer of DeiT-B, improving throughput and memory bound without performance compromise.

Blind and visually impaired (BVI) individuals face serious mobility-related risks daily due to the lack of progression in hazard detection and assistive technologies. Most existing techniques are demanding in computational resources and energy consumption, yet still struggle in real-time performance. The challenge is particularly evident when deploying these techniques on portable devices, on which lightweight coupled with sustainable low battery usage is a must. Hence in this study, we aim to leverage Genetic Programming (GP), which is well known for its feature construction capability, to develop more energy-efficient models with better features. The objective is to find more condensed features by GP, to reduce energy consumed and inference time, but without significant accuracy loss in obstacle detection from a head-mount wearable device for BVIs. Features have been trained on a series of in-door settings that represent a BVI person navigating through corridors and furniture. Models with these constructed features then are validated on actual portable board deployment, as well as on Field Programmable Gate Array simulation (FPGA). Comparative analyses are conducted using a range of performance metrics across models training by different learning methods. The metrics include accuracy, model execution time, prediction time, energy consumption, and hardware resource utilization. Our study demonstrates that GP-constructed models can generally reduce energy consumption and inference time with negligible accuracy loss. Furthermore, it can build models with higher accuracy than the benchmark, allowing users to adjust between energy usage and accuracy according to their needs.

Training-free metrics (a.k.a. zero-cost proxies) are widely used to avoid resource-intensive neural network training, especially in Neural Architecture Search (NAS). Recent studies show that existing training-free metrics have several limitations, such as limited correlation and poor generalisation across different search spaces and tasks. Hence, we propose Sample-Wise Activation Patterns and its derivative, SWAP-Score, a novel high-performance training-free metric. It measures the expressivity of networks over a batch of input samples. The SWAP-Score is strongly correlated with ground-truth performance across various search spaces and tasks, outperforming 15 existing training-free metrics on NAS-Bench-101/201/301 and TransNAS-Bench-101. The SWAP-Score can be further enhanced by regularisation, which leads to even higher correlations in cell-based search space and enables model size control during the search. For example, Spearman’s rank correlation coefficient between regularised SWAP-Score and CIFAR-100 validation accuracies on NAS-Bench-201 networks is 0.90, significantly higher than 0.80 from the second-best metric, NWOT. When integrated with an evolutionary algorithm for NAS, our SWAP-NAS achieves competitive performance on CIFAR-10 and ImageNet in approximately 6 minutes and 9 minutes of GPU time respectively.

Evolutionary neural architecture search (ENAS) has emerged as a promising approach to finding high-performance neural architectures. However, widespread application has been limited by the expensive computational costs due to the nature of evolutionary algorithms. In this study, we aim to significantly reduce the computational costs of ENAS by involving a training-free performance metric. Specifically, the network performance can be estimated by the training-free metric with only a single forward pass. However, training-free metrics have their own challenges, in particular, an insufficient correlation with ground-truth performance. We adopt a Graph Convolutional Network (GCN) based contrastive predictor which can leverage the low cost of the training-free performance metric yet improve the correlation between the estimated performance and the true performance of the candidate architectures. Combining a training-free metric - the number of linear regions with the GCN-based contrastive predictor and an active learning scheme, we propose Fast-ENAS which can achieve superior search efficiency and performance on the benchmark NAS-Bench-201 and DARTS search spaces. Furthermore, with a single GPU searching on the DARTS space, Fast-ENAS requires only 0.02 (29 minutes) and 0.026 (37 minutes) GPU days to achieve test error rates of 2.50% and 24.30% on CIFAR-10 and ImageNet respectively.

Neural architecture search (NAS) aims to automate architecture engineering in neural networks. This often requires a high computational overhead to evaluate a number of candidate networks from the set of all possible networks in the search space. Prediction of the performance of a network can alleviate this high computational overhead by mitigating the need for evaluating every candidate network. Developing such a predictor typically requires a large number of evaluated architectures which may be difficult to obtain. We address this challenge by proposing a novel evolutionary-based NAS strategy, predictor-assisted evolutionary NAS (PRE-NAS) which can perform well even with an extremely small number of evaluated architectures. PRE-NAS leverages new evolutionary search strategies and integrates high-fidelity weight inheritance over generations. Unlike one-shot strategies, which may suffer from bias in the evaluation due to weight sharing, offspring candidates in PRE-NAS are topologically homogeneous. This circumvents bias and leads to more accurate predictions. Extensive experiments on the NAS-Bench-201 and DARTS search spaces show that PRE-NAS can outperform state-of-the-art NAS methods. With only a single GPU searching for 0.6 days, a competitive architecture can be found by PRE-NAS which achieves 2.40% and 24% test error rates on CIFAR-10 and ImageNet, respectively.

Neural architecture search (NAS) aims to automate architecture engineering in neural networks. This often requires a high computational overhead to evaluate a number of candidate networks from the set of all possible networks in the search space during the search. Prediction of the networks' performance can alleviate this high computational overhead by mitigating the need for evaluating every candidate network. Developing such a predictor typically requires a large number of evaluated architectures which may be difficult to obtain. We address this challenge by proposing a novel evolutionary-based NAS strategy, Predictor-assisted E-NAS (PRE-NAS), which can perform well even with an extremely small number of evaluated architectures. PRE-NAS leverages new evolutionary search strategies and integrates high-fidelity weight inheritance over generations. Unlike one-shot strategies, which may suffer from bias in the evaluation due to weight sharing, offspring candidates in PRE-NAS are topologically homogeneous, which circumvents bias and leads to more accurate predictions. Extensive experiments on NAS-Bench-201 and DARTS search spaces show that PRE-NAS can outperform state-of-the-art NAS methods. With only a single GPU searching for 0.6 days, competitive architecture can be found by PRE-NAS which achieves 2.40% and 24% test error rates on CIFAR-10 and ImageNet respectively.

Person re-identification (re-ID), aiming to recognize a person of interest across different cameras, is a well-known challenge because of the vast variation in human poses. Existing pose-driven re-ID methods utilize keypoints, which are considered fine-grained local information, inadequate to capture global pose characteristics. In this paper we propose multi-granularity pose fusion network (MGPFNet), to address the pose variation problem. In particular we propose the use of view information in re-ID. A pose in MGPFNet is multi-granular containing the coarse-grained view and fine-grained keypoint information. Two encoding methods, namely pose concatenation encoding and pose independent encoding, are proposed to incorporate both coarse-grained views information and fine-grained keypoints information while alleviating the impact of pose variations. Extensive experiments on three benchmark datasets with views demonstrates the effectiveness of MGPFNet which outperforms state-of-the-art methods in most cases, confirming the benefit of using views in re-ID.

Generative Adversarial Networks (GAN) are well known for their capability of generating photo-realistic images or data collections that appear real. One of state-of-the-art approaches in GAN is Evolutionary GAN (E-GAN) which can outperform other GAN methods by leveraging the advantages of evolutionary computing, including population based search, mutation and elitism operators. However evolutionary search is often demanding in terms of resources, e.g. computational power and time. That limits its applicability when resource is limited. Hence we propose Partial Transfer training based E-GAN (PT-EGAN) to improve the efficiency of E-GAN. PT-EGAN aims to train the generator and the discriminator with smaller data sets and transfer the gained features across different stages of training. Our comparative experiments on the CIFAR-10 data set shows that PT-EGAN can reach better performance than E-GAN when using similar resources. Alternatively PT-EGAN requires less resources to achieve a similar performance as E-GAN. PT-EGAN is effective in speeding up generative adversarial learning.

Existing research on parking availability sensing mainly relies on extensive contextual and historical information. In practice, the availability of such information is a challenge as it requires continuous collection of sensory signals. In this study, we design an end-to-end transfer learning framework for parking availability sensing to predict parking occupancy in areas in which the parking data is insufficient to feed into data-hungry models. This framework overcomes two main challenges: 1) many real-world cases cannot provide enough data for most existing data-driven models, and 2) it is difficult to merge sensor data and heterogeneous contextual information due to the differing urban fabric and spatial characteristics. Our work adopts a widely-used concept, adversarial domain adaptation, to predict the parking occupancy in an area without abundant sensor data by leveraging data from other areas with similar features. In this paper, we utilise more than 35 million parking data records from sensors placed in two different cities, one a city centre and the other a coastal tourist town. We also utilise heterogeneous spatio-temporal contextual information from external resources, including weather and points of interest. We quantify the strength of our proposed framework in different cases and compare it to the existing data-driven approaches. The results show that the proposed framework is comparable to existing state-of-the-art methods and also provide some valuable insights on parking availability prediction.

Existing parking recommendation solutions mainly focus on finding and suggesting parking spaces based on the unoccupied options only. However, there are other factors associated with parking spaces that can influence someone’s choice of parking such as fare, parking rule, walking distance to destination, travel time, likelihood to be unoccupied at a given time. More importantly, these factors may change over time and conflict with each other which makes the recommendations produced by current parking recommender systems ineffective. In this paper, we propose a novel problem called multi-objective parking recommendation. We present a solution by designing a multi-objective parking recommendation engine called MoParkeR that considers various conflicting factors together. Specifically, we utilise a non-dominated sorting technique to calculate a set of Pareto-optimal solutions, consisting of recommended trade-off parking spots. We conduct extensive experiments using two real-world datasets to show the applicability of our multi-objective recommendation methodology.

Large-scale optimisation is of great importance as most real-world optimisation problems involve a large number of decision variables. Cooperative co-evolution (CC) approaches are successful in this field as they can tackle thousands of decision variables. CC methods consist of decomposition, optimisation of decomposed sub-components and cooperative combination based on the `divide-and-conquer' mechanism. Sub-components are optimised cooperatively before the merge. Most of existing CCs optimise different sub-components using the same optimisation algorithm. In this study we propose an adaptive approach based on multi-optimiser cooperative co-evolution for large-scale optimisation problems. As different sub-components may have different characteristics and different contributions towards the global fitness function, they should to be handled differently considering the diversity and the quality of each sub-component. To achieve this effect our proposed approach incorporates four different optimisers adaptively according to the relative contribution. In each optimisation cycle, an adaptive selection strategy is used to allocate the most suited optimiser to each sub-component using quality-diversity measure and the historical performance of the algorithms. The performance of the proposed approach has been evaluated on large-scale optimisation benchmark problems. The results confirmed the effectiveness of the proposed adaptive approach as it can achieve comparable or better performance on almost of test cases compared to state-of-the-art methods.

Swarm robots continue to become more prominent in solving challenging tasks in real world applications. Due to the complexity of operating in often unknown environments, centralised control of swarm robots is not ideal. Prior manual programming is also not practical under these kind of circumstances. Thus, we establish a hyper-heuristic based learning approach for swarm robot control. With this framework, robots can autonomously identify appropriate heuristics from a set of given low-level heuristics, each heuristic guiding certain behaviours. We evaluated this type of online learning on building surface cleaning and studied the effectiveness of our hyper-heuristic online learning. Nine heuristics were proposed in this study. Through the experiments it can be seen that robots can improve their cleaning performance through the online learning process. More importantly, the experiments show that appropriate heuristics can be selected even when the size of the heuristic set is changed. The study on four types of environments shows that with the same heuristic set, the robot swarm can adapt to different environments for different tasks. Hence, hyper-heuristic learning is an effective method for decentralised control of swarm robots.

Project Scheduling Problem (PSP) plays a crucial role in large-scale software development, directly affecting the productivity of the team and on-time delivery of software projects. PSP concerns with the decision of who does what and when during the software project lifetime. PSP is a combinatorial optimisation problem and inherently NP-hard, indicating that approximation algorithms are highly advisable for real-world instances which are often large in size. In this work, we propose an iterated local search (ILS) algorithm for PSP. ILS is a simple, yet effective for combinatorial optimisation problems. However, its performance highly depends on its perturbation operator which is to guide the search to new starting points. Hereby, we propose a Genetic Programming (GP) approach to evolve perturbation operators based on a range of low-level operators and rules. The evolution process will go along with the iterated search process and supply better operators continuously. The GP based ILS algorithm is tested using a set of well known PSP benchmark instances and compared with state-of-the-art algorithms. The experimental results demonstrated the effectiveness of GP generated perturbation operators as they can outperform existing leading methods.

In this paper, a novel bi-level grouping optimization (BIGO) model is proposed for solving the storage location assignment problem with grouping constraint (SLAP-GC). A major challenge in this problem is the grouping constraint which restricts the number of groups each product can have and the locations of items in the same group. In SLAP-GC, the problem consists of two subproblems, one is how to group the items, and the other one is how to assign the groups to locations. It is an arduous task to solve the two subproblems simultaneously. To overcome this difficulty, we propose a BIGO. BIGO optimizes item grouping in the upper level, and uses the lower-level optimization to evaluate each item grouping. Sophisticated fitness evaluation and search operators are designed for both upper and lower level optimization so that the feasibility of solutions can be guaranteed, and the search can focus on promising areas in the search space. Based on the BIGO model, a multistart random search method and a tabu search algorithm are proposed. The experimental results on the real-world dataset validate the efficacy of the BIGO model and the advantage of the tabu search method over the random search method.

Deep Belief Networks (DBN) have been successful in classification especially image recognition tasks. However, the performance of a DBN is often highly dependent on settings in particular the combination of runtime parameter values. In this work, we propose a hyper-heuristic based framework which can optimise DBNs independent from the problem domain. It is the first time hyper-heuristic entering this domain. The framework iteratively selects suitable heuristics based on a heuristic set, apply the heuristic to tune the DBN to better fit with the current search space. Under this framework the setting of DBN learning is adaptive. Three well-known image reconstruction benchmark sets were used for evaluating the performance of this new approach. Our experimental results show this hyper-heuristic approach can achieve high accuracy under different scenarios on diverse image sets. In addition state-of-the-art meta-heuristic methods for tuning DBN were introduced for comparison. The results illustrate that our hyper-heuristic approach can obtain better performance on almost all test cases.

Optimisation under dynamic environment is a well known challenge not only because of the difficulties in handling constant changes during the search progress but also because of its real-world implication as many industry environments are dynamic. To tackle the dynamic aspect, optimisation algorithms need to track the changes and adjust for the global optima simultaneously. In this paper, we propose a multi-population memetic algorithm for dynamic optimisation, specially for the dynamic shortest path routing (DSPR) problem in mobile ad-hoc networks. DSPR is to find the shortest possible path that connects a source node with the destination node under a network environment where the topology is dynamic. There are algorithms proposed for DSPR. However handling the dynamic environment while maintaining the diversity is still a major issue. Hence the multi-population memetic algorithm is designed which has four main parts so the balance between exploration and exploitation of the search space could be better maintained. They include a genetic algorithm part which focuses solely on the exploring the search space; a local search component which is to search around the local area; a multi-population mechanism which is to maintain diversity by allocating every sub-population to different search area; and an external archive which is to preserve the current best solutions. The proposed method has been evaluated on DSPR instances that are generated under both cyclic and acyclic environments. Results show that the proposed algorithm can outperform other methods reported in the literature. That indicates the effectiveness of our proposed multi-population memetic approach in dealing with dynamic optimisation problems.

Load balancing (LB) is crucial in the field of cloud computing. LB is to find the optimum allocation of services onto a set of machines so the machine usage can be maximised. This paper proposes a new method for LB, simulated annealing (SA) enhanced by grammatical evolution (GE). SA is a well-known stochastic optimisation algorithm that has good performance on a range of problems including loading balancing. However the success of SA often relies on a key parameter known as the cooling schedule and the type of the utilised neighbourhood structure. Both the parameter and the structure of SA are problem specific. They need to be manually adjusted to fit the problem in hand. In addition different stages of the search process may have different optimal parameter values. To address these issues, a grammar evolution approach is introduced to adaptively evolve the cooling schedule parameter and neighbourhood structures. The proposed method can adjust SA parameter and structure based on the landscape of the current search state so high quality solutions can be found more quickly. The effectiveness of the proposed GE method is demonstrated on the Google machine reassignment problem, which is a typical LB problem, proposed for the ROADEF/EURO 2012 challenge. Experimental results show that our GE enhanced SA is highly competitive compared to state-of-the-art algorithms.

Data center efficiency is primarily sought by sharing physical resources, such as processors, memory, and disks in the form of virtual machines or containers among multiple users, i.e., workload consolidation. However, the reality is co-located applications in these virtual platforms compete for resources and interfere with each others' performance, resulting in performance variability/degradation. In this paper, we present the contentionaware resource allocation (CARA) solution, which optimizes data center efficiency. It is essentially devised based on a model predictive control that enables to make judicious consolidation decisions with future system states. CARA consolidates workloads explicitly taking into account the correlation between shared and isolated resource usage patterns. Based on our experimental results, CARA improves the overall resource utilization by 32%, without a significant impact on the quality-of-service (QoS) enforcement level. Such improvement results in a fewer number of active servers and in turn contributes to an overall energy saving by 33%.

We propose a model for clustering data with spatiotemporal intervals. This model is used to effectively evaluate clusters of spatiotemporal interval data. A new energy function is used to measure similarity and balance between clusters in spatial and temporal dimensions. We employ as a case study a large collection of parking data from a real CBD area. The proposed model is applied to existing traditional algorithms to address spatiotemporal interval data clustering problem. Results from traditional clustering algorithms are compared and analysed using the proposed energy function.

In recent years, wireless sensor networks have been widely used in healthcare applications, such as hospital and home patient monitoring. Wireless medical sensor networks are more vulnerable to eavesdropping, modification, impersonation and replaying attacks than the wired networks. A lot of work has been done to secure wireless medical sensor networks. The existing solutions can protect the patient data during transmission, but cannot stop the inside attack where the administrator of the patient database reveals the sensitive patient data. In this paper, we propose a practical approach to prevent the inside attack by using multiple data servers to store patient data. The main contribution of this paper is securely distributing the patient data in multiple data servers and employing the Paillier and ElGamal cryptosystems to perform statistic analysis on the patient data without compromising the patients' privacy.

Vehicle routing is known as the most challenging but an important problem in the transportation and logistics filed. The task is to optimise a set of vehicle routes to serve a group of customers with minimal delivery cost while respecting the problem constraints such as arriving within given time windows. This study presented a math-hyper-heuristic approach to tackle this problem more effectively and more efficiently. The proposed approach consists of two phases: a math phase and a hyper-heuristic phase. In the math phase, the problem is decomposed into sub-problems which are solved independently using the column generation algorithm. The solutions for these sub-problems are combined and then improved by the hyper-heuristic phase. Benchmark instances of large-scale vehicle routing problems with time windows were used for evaluation. The results show the effectiveness of the math phase. More importantly the proposed method achieved better solutions in comparison with two state of the art methods on all instances. The computational cost of the proposed method is also lower than that of other methods.

The Storage Location Assignment Problem (SLAP) is a significant optimisation problem in warehouse management. Given a number of products, each with a set of items with different popularities (probabilities of being ordered), SLAP is to find the best locations for the items of the products in the warehouse to minimise the warehouse operational cost. Specifically, the operational cost is the expected cost of picking the orders. Grouping constraints are included to take the practical considerations into account in the problem. That is, the items belonging to the same product are more desirable to be placed together. In this paper, the SLAP with Grouping Constraints (SLAP-GC) is investigated, and an efficient Restricted Neighbourhood Tabu Search (RNTS) algorithm is proposed to solving it. RNTS adopts the problem-specific search operators to maintain solution feasibility, and the tabu list to prevent searching back and forth. RNTS was empirically compared with the mathematical programming method and a previously designed Genetic Programming method, which is demonstrated to be the state-of-the-art algorithm for SLAP-GC. The experimental results on the real-world data show that RNTS outperforms the state-of-the-art algorithms for SLAP-GC in terms of solution quality and speed. It managed to achieve optimal solutions for most of the small-scale instances much faster and outperformed the Genetic Programming method in terms of both solution quality and running time on all the test instances.

The shortest path routing (SPR) problem is a well-known challenge in the field of mobile network routing. The aim is to find the least cost path that connect a specific source node with a specific destination node. Although there are numerous algorithms to solve SPR, most of them consider only static environments in which the network topology and link-cost never change. A network with dynamic topologies and cost are indeed more challenging but more practical in real world applications. This paper presents a memetic algorithm for dynamic SPR (DSPR) problems in a mobile network. The proposed approach consists of three stages: genetic algorithm, local search and elitism-based immigrants procedure. Genetic algorithm (GA) is applied in the first stage to explore the search space and generate a new set of solutions. The generated solutions are further improved in the second stage by a local search algorithm. In third stage, an elitism-based immigrants procedure is activated to handle the dynamic changes by maintaining the diversity of the search process. The performance of the proposed algorithm has been evaluated on dynamic shortest path routing problem instances under both cyclic and acyclic environments. The study shows that, on both circumstances, the proposed algorithm is very stable with regards to dynamic network changes. This method is highly competitive compared to state-of-the-art algorithms in the literature as it outperformed these algorithms on all instances of dynamic routing during evaluation.

This study proposes a method for solving real-world warehouse Storage Location Assignment Problem (SLAP) under grouping constraints by Genetic Programming (GP). Integer Linear Programming (ILP) formulation is used to define the problem. By the proposed GP method, a subset of the items is repeatedly selected and placed into the available current best location of the shelves in the warehouse, until all the items have been assigned with locations. A heuristic matching function is evolved by GP to guide the selection of the subsets of items. Our comparison between the proposed GP approach and the traditional ILP approach shows that GP can obtain near-optimal solutions on the training data within a short period of time. Moreover, the evolved heuristics can achieve good optimization results on unseen scenarios, comparable to that on the scenario used for training. This shows that the evolved heuristics have good reusability and can be directly applied for slightly different scenarios without any new search process.

Activity recognition from smartphone sensor inputs is of great importance to enhance user experience. Our study aims to investigate the applicability of Genetic Programming (GP) approach on this complex real world problem. Traditional methods often require substantial human efforts to define good features. Moreover the optimal features for one type of activity may not be suitable for another. In comparison, our GP approach does not require such feature extraction process, hence, more suitable for complex activities where good features are difficult to be pre-defined. To facilitate this study we therefore propose a benchmark of activity data collected from various smartphone sensors, as currently there is no existing publicly available database for activity recognition. In this study, a GP-based approach is applied to nine types of activity recognition tasks by directly taking raw data instead of features. The effectiveness of this approach can be seen by the promising results. In addition our benchmark data provides a platform for other machine learning algorithms to evaluate their performance on activity recognition.

Elderly people are prone to fall due to the high rate of risk factors associated with ageing. Existing fall detection systems are mostly designed for a constrained environment, where various assumptions are applied. To overcome these drawbacks, we opt to use mobile phones with standard built-in sensors. Fall detection is performed on motion data collected by sensors in the phone alone. We use Genetic Programming (GP) to learn a classifier directly from raw sensor data. We compare the performance of GP with the popular approach of using threshold-based algorithm. The result shows that GP-evolved classifiers perform consistently well across different fall types and overall more reliable than the threshold-based.

In this paper, we propose a novel hybrid classification method which is based on two distinct approaches, namely Genetic Programming (GP) and Nearest Neighbour (kNN). The method relies on a memory list which contains some correctly labelled instances and is formed by classifiers evolved by GP. The class label of a new instance will be determined by combining its most similar instances in the memory list and the output of GP classifier on this instance. The results show that this proposed method can outperform conventional GP-based classification approach. Compared with conventional classification methods such as Naive Bayes, SVM, Decision Trees, and conventional kNN, this method can also achieve better or comparable accuracies on a set of binary problems. The evaluation cost of this hybrid method is much lower than that of conventional kNN.

Recognizing text captured in a photograph, or scene text, remains an unsolved problem in computer vision. Conventional methods require a complex multi-step process to incorporate a pipeline of manually constructed algorithms. In contrast this research presents a single step framework which is based on Genetic Programming (GP). With a suitable methodology, character recognition programs can be automatically generated which are capable of handling common challenges in scene text including gradated foreground and background, low contrast, variations in size and font, without specific components designed for these challenges. Furthermore, the solutions evolved by GP are capable of handling a degree of blur and rotation without adding any extra mechanisms into the proposed GP framework. We also show that GP programs trained on synthetic images can recognize characters in real scene text images, which indicates that some genuine characteristics of text have been captured by these programs. This research lays a foundation toward a scene text recognition method which does not rely on complex preprocessing, localisation and feature extraction processes. This work shows that it is possible to evolve character recognition programs with minimal human effort.

This paper describes an approach to the detection rice plants in images of rice fields by using genetic programming. The method involves the evolution of a genetic programming classifier of 20 × 20 pixel windows to distinguish rice and nonrice windows, applies the evolved classifier to each pixel position in a test image in a scanning window fashion and determines the class of a pixel by majority voting. The individual pixel values in the window comprise the terminal set. The four arithmetic operators, augmented by square root, comprise the function set. Fitness is a weighted sum of true positive and true negative rates. The classifier achieves an accuracy of 90% on positive and negative windows and is highly accurate in localizing rice leaves in test images for micro-spraying of nutritional supplements. The evolutionary approach clearly outperforms a thresholding approach based on colour which is unable to distinguish between rice an leaves.

Compared to conventional activity recognition methods using feature extraction followed by classification, the Genetic Programming (GP) based classification applied to raw sensor data can avoid the time-consuming and knowledge-dependent feature extraction procedure. However, the traditional GP-based classifier using accuracy as fitness function is sensitive to the choice of threshold values. Furthermore, sensor data of the same activity might demonstrate remarkable distinction when the signal is collected in the changing environment, which will lead to inconsistency between training and testing data and consequently degrade the generalization power of the trained classifier. Moreover, the GP-based classifier cannot well distinguish less separable activities in the presence of multiple activities. Our work aims to address these issues by improving the GP-based classifier via: (1) using the area under the receiver operating characteristic curve (AUC) as fitness function, (2) using an online local time series normalization procedure to pre-smooth undesirable features, and (3) using a binary tree based classification framework to force GP to learn key discriminating features that can better distinguish less separable activities. We test the proposed method on a sensor data set collected from a smartphone, consisting of four common human activities, sitting, standing, walking and running. The proposed GP-based classifier achieves the outstanding performance on recognizing each of four activities in terms of both high true positive and low false alarm rates, which much improves over the traditional GP-based classifier and several of its variants.

Recognition of activities such as sitting, standing, walking and running can significantly improve the interaction between human and machine, especially on mobile devices. In this study we present a GP based method which can automatically evolve recognition programs for various activities using multisensor data. This investigation shows that GP is capable of achieving good recognition on binary problems as well as on multi-class problems. With this method domain knowledge about an activity is not required. Furthermore, extraction of time series features is not necessary. The investigation also shows that these evolved GP solutions are small in size and fast in execution. They are suitable for real-world applications which may require real-time performance.

A novel approach is proposed in this study, which is to evolve visual inspection programs for automatic defect detection on populated printed circuit boards. This GP-based method does not require knowledge of the layout design of a board, nor relevant domain knowledge such as lighting conditions and visual characteristics of the components. Furthermore, conventional image operators are not required to perform the detection. The experiments show that these evolved GP programs can identify all the faults while some suspicious areas are also highlighted. By this GP approach, manual inspection effort can be dramatically reduced. In addition, an evolved GP detection program can readily work on different types of boards without re-training.

Loop structure is a fundamental flow control in programming languages for repeating certain operations. It is not widely used in Genetic Programming as it introduces extra complexity in the search. However in some circumstances, including a loop structure may enable GP to find better solutions. This study investigates the benefits of loop structures in evolving GP classifiers. Three different loop representations are proposed and compared with other GP methods and a set of traditional classification methods. The results suggest that the proposed loop structures can outperform other methods. Additionally the evolved classifiers can be small and simple to interpret. Further analysis on a few classifiers shows that they indeed have captured genuine characteristics from the data for performing classification.

Image classification is a complex but important task especially in the areas of machine vision and image analysis such as remote sensing and face recognition. One of the challenges in image classification is finding an optimal set of features for a particular task because the choice of features has direct impact on the classification performance. However the goodness of a feature is highly problem dependent and often domain knowledge is required. To address these issues we introduce a Genetic Programming (GP) based image classification method, Two-Tier GP, which directly operates on raw pixels rather than features. The first tier in a classifier is for automatically defining features based on raw image input, while the second tier makes decision. Compared to conventional feature based image classification methods, Two-Tier GP achieved better accuracies on a range of different tasks. Furthermore by using the features defined by the first tier of these Two-Tier GP classifiers, conventional classification methods obtained higher accuracies than classifying on manually designed features. Analysis on evolved Two-Tier image classifiers shows that there are genuine features captured in the programs and the mechanism of achieving high accuracy can be revealed. The Two-Tier GP method has clear advantages in image classification, such as high accuracy, good interpretability and the removal of explicit feature extraction process.

Genetic Programming (GP) is reputable for its power in finding creative solutions for complex problems. However the downside of it is also well known: the evolved solutions are often difficult to understand. This interpretability issue hinders GP to gain acceptance from many application areas. To address this issue in the context of motion detection, GP programs evolved for various detection tasks are analyzed in this study. Previous work has shown the capabilities of these evolved motion detectors such as ignoring uninteresting motions, differentiating fast motions from slow motions, identifying genuine motions from a moving background, and handling noises. This study aims to reveal the behavior of these GP individuals by introducing simplified motion detection tasks. The investigation on these GP motion detectors shows that their good performance is not random. There are contributing characteristics captured by these detectors, of which the behaviors are more or less explainable. This study validates GP as a good approach for motion detection.

This paper extends the application of Genetic Programming into a new area, automatically splitting video frames based on the content. A GP methodology is presented to show how to evolve a program which can analyse the difference between scenes and split them accordingly. The evolved video splitting programs achieve reasonable performance even when the videos are not easily recognizable by eyes due to the server artificial noises. Moreover, a few different approaches have been investigated in this study. We compare the performance of GP with J48, NaïveBayes and one video splitting software, the experimental results show that GP generated splitters are comparable with two conventional machine learning algorithms and more accurate than human written program.

The aim of event detection in time series is to identify particular occurrences of user-interest in one or more time lines, such as finding an anomaly in electrocardiograms or reporting a sudden variation of voltage in a power supply. Current methods are not adequate for detecting certain kinds of events without any domain knowledge. Therefore, we propose a Genetic Programming (GP) based event detection methodology in which solutions can be built from raw time series data. The framework is applied to five synthetic data sets and one real world application. The experimental results show that working on raw data even with a dimensionality as high as 140 × 80, genetic programming can achieve superior performance to conventional methods operating on pre-defined features. Furthermore, analysis of the evolved event detectors shows that they have captured the regularities inserted into the synthetic data sets and some individuals can be readily understood by humans.

This study presents a selective motion detection methodology which is based on genetic programming (GP), an evolutionary search strategy. By this approach, motion detection programs can be automatically evolved instead of manually coded. This study investigates the suitable GP representation for motion detection as well as explores the advantages of this method. Unlike conventional methods, this evolutionary approach can generate programs which are able to mark target motions. The stationary background and the uninteresting or irrelevant motions such as swaying trees, noises are all ignored. Furthermore, programs can be trained to detect target motions from a moving background. They are capable of distinguishing different kinds of motions. Such differentiation can be based on the type of motions as well, for example, fast moving targets are captured, while slow moving targets are ignored. One of the characteristics of this method is that no modification or additional process is required when different types of motions are introduced. Moreover, real-time performance can be achieved by this GP motion detection method.

Motion detection is a vital part of vision systems, either biological or computerized. Conventional motion detection methods in machine vision can differentiate moving objects from background, but cannot directly handle different types of motions. In this paper, we present Genetic Programming (GP) as a method which not only removes relatively stationary background, but also can be selective on what kind of motions to capture. Programs can be evolved to select a certain type of moving objects and ignore other motions. That is to select fast moving target and ignore slowing moving ones. Furthermore programs can be evolved to handle these tasks even when the camera itself is in relatively arbitrary motion. This general GP method does not require additional process to differentiate various types of motions.

Unnecessary growth in program size is known as the bloat problem in Genetic Programming. Bloat not only increases computational expenses during evolution, but also impairs the understandability and execution performance of evolved final solutions. There are a large number of studies addressing this problem. In this paper, we present an effective bloat control mechanism which is based on examining the contribution of each function node in the selected programs. Nodes without contribution will be removed before generating offspring. This method has been applied to various tasks. The results show that it can significantly reduce program size without damping the fitness of individuals. In some cases it increases the performance of the final solutions. Furthermore it does not require extra computational resources to perform the control whilst it speeds up evolution processes because of the saving in evaluation costs.

Detecting moving objects is a significant component in many machine vision systems. One of the challenges in real world motion detection is the unstability of the background. An ideal method is expected to reliably detect interesting movements from videos while ignoring background/uninteresting movements. In this paper, Genetic Programming (GP) based motion detection method is used to tackle this issue, as it is a powerful learning method and has been successfully applied on various image analysis tasks. The investigation here focuses on the various representations of GP for motion detection and the suitability of these approaches. The unstable environments in this study include ripples on river, rainy background and moving cameras. It can be shown from the results that with a suitable frame representation and function set, reliable GP programs can be evolved to handle complex unstable background.

Unnecessary growth in program size is known as bloat problem in Genetic Programming. There are a large number of studies addressing this problem. In this paper, we propose an effective bloat control mechanism which is based on examining the contribution of each function node in the selected programs. Nodes without contribution will be removed before generating offspring. The results show that the method can significantly reduce program size without compromising fitness. Furthermore it speeds up evolution processes because of the saving in evaluation costs.

Genetic programming has been applied to various types of vision tasks. This paper extends the use of this powerful problem solving method to a more complex but more common domain, video analysis. We present the methodology as well as the experiments on two video analysis tasks: segmenting texture regions and detecting moving objects. The advantages of GP in this domain can be shown by this study. Firstly GP methods are less dependent on knowledge from domain experts. One methodology is suitable for both tasks. Secondly GP can generate fast video frame analyzers which are highly desirable or even critical in real time vision applications.

In this paper we investigated the use of Genetic Programming (GP) to evolve programs which could detect moving objects in videos. Two main approaches under the paradigm were proposed and investigated, single-frame approach and multi-frame approach. The former is based on analyzing individual video frames and treat them independently while the latter approach consider a sequence of frames. In the single-frame approach, three methods are investigated including using pixel intensity, pixel hue value and feature values. The experiments on Robosoccer field show that GP could detect the target under different lighting conditions and could even handle arbitrary camera positions. Although there was no domain knowledge had been provided during evolution, GP was able to produce moving object detectors that were robust and fast.

This paper describes a texture segmentation method using genetic programming (GP), which is one of the most powerful evolutionary computation algorithms. By choosing an appropriate representation texture, classifiers can be evolved without computing texture features. Due to the absence of time-consuming feature extraction, the evolved classifiers enable the development of the proposed texture segmentation algorithm. This GP based method can achieve a segmentation speed that is significantly higher than that of conventional methods. This method does not require a human expert to manually construct models for texture feature extraction. In an analysis of the evolved classifiers, it can be seen that these GP classifiers are not arbitrary. Certain textural regularities are captured by these classifiers to discriminate different textures. GP has been shown in this study as a feasible and a powerful approach for texture classification and segmentation, which are generally considered as complex vision tasks.

Program Bloat - phenomenon of ever-increasing program size during a GP run - is a recognised and widespread problem. Traditional techniques to combat program bloat are program size limitations of parsimony pressure (penalty functions). These techniques suffer from a number of problems, in particular their reliance on parameters whose optimal values it is difficult to a priori determine. In this paper, we introduce POPE-GP, a system that makes use of the NSGA-II multiobjective evolutionary algorithm as an alternative, parameter-free technique for eliminating program bloat. We test it on a classification problem and find that while vastly reducing program size, it does improve generalisation performance.

This work presents the use of genetic programming (GP) to a complex domain, texture analysis. Two major tasks of texture analysis, texture classification and texture segmentation, are studied. Bitmap textures are used in this investigation. In classification tasks, the results show that GP is able to evolve accurate classifiers based on texture features. Moreover by using the presented method, GP is able to evolve accurate classifiers without extracting texture features. In texture segmentation tasks, the investigation shows that a fast and accurate segmentation method can be developed based on GP generated texture classifiers. Our further investigation show that the accuracies are not achieved by chance. There are regularities been captured by GP-generated classifiers in performing texture discrimination.

This paper presents a method which extends the use of genetic programming (GP) to a complex domain, texture segmentation. By this method, segmentation tasks are performed by texture classifiers which are evolved by the GP. Small cutouts sampled from images of various textures are used for the evolution. The generated classifiers directly use pixel values as input. Based on these classifiers an algorithm which uses a voting strategy to partition texture regions is developed. The results of the investigation indicate that the proposed method is able to accurately identify the boundaries between different texture regions, even if the boundaries are not regular. The method can segment two textures as well as multiple textures. Furthermore, fast segmentation can be achieved. The speed of the proposed texture segmentation method can be a hundred times faster than conventional methods.

We investigate the behaviour of image texture classifiers generated by genetic programming. We propose techniques to understand how classifiers capture textural characteristics and for discussing the effectiveness of different classifiers. Our results show that regularities of patterns can be detected by the genetic programming method without predefined knowledge.