On the Performance of Polynomial-time CLIQUE Approximation Algorithms on Very Large Graphs

The performance of a randomized version of the subgraph-exclusion algorithm (called Ramsey) for CLIQUE by Boppana and Halldorsson is studied on very large graphs. We compare the performance of this algorithm with the performance of two common heuristic algorithms, the greedy heuristic and a version of simulated annealing. These algorithms are tested on graphs with up to 10,000 vertices on a workstation and graphs as large as 70,000 vertices on a Connection Machine. Our implementations establish the ability to run clique approximation algorithms on very large graphs. We test our implementations on a variety of different graphs. Our conclusions indicate that on randomly generated graphs minor changes to the distribution can cause dramatic changes in the performance of the heuristic algorithms. The Ramsey algorithm, while not as good as the others for the most common distributions, seems more robust and provides a more even overall performance. In general, and especially on deterministically generated graphs, a combination of simulated annealing with either the Ramsey algorithm or the greedy heuristic seems to perform best. This combined algorithm works particularly well on large Keller and Hamming graphs and has a competitive overall performance on the DIMACS benchmark graphs.

On the Effectiveness of Genetic Search in Combinatorial Optimization

In this paper, we study the efficacy of genetic algorithms in the context of combinatorial optimization. In particular, we isolate the effects of cross-over, treated as the central component of genetic search. We show that for problems of nontrivial size and difficulty, the contribution of cross-over search is marginal, both synergistically when run in conjunction with mutation and selection, or when run with selection alone, the reference point being the search procedure consisting of just mutation and selection. The latter can be viewed as another manifestation of the Metropolis process. Considering the high computational cost of maintaining a population to facilitate cross-over search, its marginal benefit renders genetic search inferior to its singleton-population counterpart, the Metropolis process, and by extension, simulated annealing. This is further compounded by the fact that many problems arising in practice may inherently require a large number of state transitions for a near-optimal solution to be found, making genetic search infeasible given the high cost of computing a single iteration in the enlarged state-space.

Systematic delay-driven power optimisation and power-driven delay optimisation of combinational circuits

With the proliferation of mobile wireless communication and embedded systems, the energy efficiency becomes a major design constraint. The dissipated energy is often referred as the product of power dissipation and the input-output delay. Most of electronic design automation techniques focus on optimising only one of these parameters either power or delay. Industry standard design flows integrate systematic methods of optimising either area or timing while for power consumption optimisation one often employs heuristics which are characteristic to a specific design. In this work we answer three questions in our quest to provide a systematic approach to joint power and delay Optimisation. The first question of our research is: How to build a design flow which incorporates academic and industry standard design flows for power optimisation? To address this question, we use a reference design flow provided by Synopsys and integrate in this flow academic tools and methodologies. The proposed design flow is used as a platform for analysing some novel algorithms and methodologies for optimisation in the context of digital circuits. The second question we answer is: Is possible to apply a systematic approach for power optimisation in the context of combinational digital circuits? The starting point is a selection of a suitable data structure which can easily incorporate information about delay, power, area and which then allows optimisation algorithms to be applied. In particular we address the implications of a systematic power optimisation methodologies and the potential degradation of other (often conflicting) parameters such as area or the delay of implementation. Finally, the third question which this thesis attempts to answer is: Is there a systematic approach for multi-objective optimisation of delay and power? A delay-driven power and power-driven delay optimisation is proposed in order to have balanced delay and power values. This implies that each power optimisation step is not only constrained by the decrease in power but also the increase in delay. Similarly, each delay optimisation step is not only governed with the decrease in delay but also the increase in power. The goal is to obtain multi-objective optimisation of digital circuits where the two conflicting objectives are power and delay. The logic synthesis and optimisation methodology is based on AND-Inverter Graphs (AIGs) which represent the functionality of the circuit. The switching activities and arrival times of circuit nodes are annotated onto an AND-Inverter Graph under the zero and a non-zero-delay model. We introduce then several reordering rules which are applied on the AIG nodes to minimise switching power or longest path delay of the circuit at the pre-technology mapping level. The academic Electronic Design Automation (EDA) tool ABC is used for the manipulation of AND-Inverter Graphs. We have implemented various combinatorial optimisation algorithms often used in Electronic Design Automation such as Simulated Annealing and Uniform Cost Search Algorithm. Simulated Annealing (SMA) is a probabilistic meta heuristic for the global optimization problem of locating a good approximation to the global optimum of a given function in a large search space. We used SMA to probabilistically decide between moving from one optimised solution to another such that the dynamic power is optimised under given delay constraints and the delay is optimised under given power constraints. A good approximation to the global optimum solution of energy constraint is obtained. Uniform Cost Search (UCS) is a tree search algorithm used for traversing or searching a weighted tree, tree structure, or graph. We have used Uniform Cost Search Algorithm to search within the AIG network, a specific AIG node order for the reordering rules application. After the reordering rules application, the AIG network is mapped to an AIG netlist using specific library cells. Our approach combines network re-structuring, AIG nodes reordering, dynamic power and longest path delay estimation and optimisation and finally technology mapping to an AIG netlist. A set of MCNC Benchmark circuits and large combinational circuits up to 100,000 gates have been used to validate our methodology. Comparisons for power and delay optimisation are made with the best synthesis scripts used in ABC. Reduction of 23% in power and 15% in delay with minimal overhead is achieved, compared to the best known ABC results. Also, our approach is also implemented on a number of processors with combinational and sequential components and significant savings are achieved.

Density functional study of reactions of phenoxides with polycarbonate

Density functional calculations with simulated annealing have been used to study the reactions of chains of bisphenol A polycarbonate (BPA-PC) with sodium phenoxide (NaOPh), diphenyl carbonate (DPC), and tetraphenylphosphonium phenoxide (PPh4OPh). These calculations extend our work on the reactions of LiOPh, NaOPh, and phenol with the cyclic tetramer of BPA-PC. We study, in particular, chain growth catalyzed by NaOPh and PPh4OH. The energy barriers for reactions with PPh4OPh are somewhat larger than those involving LiOPh and NaOPh, but they are significantly lower than those involving phenol (HOPh), due in part to the collective rearrangement of phenyl groups in the reacting molecules. We discuss in the Appendix the bonds between alkali metal atoms (Na in the present calculations) and other atoms (here oxygen) that are analogous to the more familiar "hydrogen bonds".

Stochastic protein folding simulation in the three-dimensional HP-model

We present results from three-dimensional protein folding simulations in the HP-model on ten benchmark problems. The simulations are executed by a simulated annealing-based algorithm with a time-dependent cooling schedule. The neighbourhood relation is determined by the pull-move set. The results provide experimental evidence that the maximum depth D of local minima of the underlying energy landscape can be upper bounded by D < n(2/3). The local search procedure employs the stopping criterion (In/delta)(D/gamma) where m is an estimation of the average number of neighbouring conformations, gamma relates to the mean of non-zero differences of the objective function for neighbouring conformations, and 1-delta is the confidence that a minimum conformation has been found. The bound complies with the results obtained for the ten benchmark problems. (c) 2008 Elsevier Ltd. All rights reserved.

Population-based local search for protein folding simulation in the MJ energy model and cubic lattices

We present experimental results on benchmark problems in 3D cubic lattice structures with the Miyazawa-Jernigan energy function for two local search procedures that utilise the pull-move set: (i) population-based local search (PLS) that traverses the energy landscape with greedy steps towards (potential) local minima followed by upward steps up to a certain level of the objective function; (ii) simulated annealing with a logarithmic cooling schedule (LSA). The parameter settings for PLS are derived from short LSA-runs executed in pre-processing and the procedure utilises tabu lists generated for each member of the population. In terms of the total number of energy function evaluations both methods perform equally well, however. PLS has the potential of being parallelised with an expected speed-up in the region of the population size. Furthermore, both methods require a significant smaller number of function evaluations when compared to Monte Carlo simulations with kink-jump moves. (C) 2009 Elsevier Ltd. All rights reserved.

A Hybrid Evolutionary Approach to the Nurse Rostering Problem

Nurse rostering is a difficult search problem with many constraints. In the literature, a number of approaches have been investigated including penalty function methods to tackle these constraints within genetic algorithm frameworks. In this paper, we investigate an extension of a previously proposed stochastic ranking method, which has demonstrated superior performance to other constraint handling techniques when tested against a set of constrained optimisation benchmark problems. An initial experiment on nurse rostering problems demonstrates that the stochastic ranking method is better in finding feasible solutions but fails to obtain good results with regard to the objective function. To improve the performance of the algorithm, we hybridise it with a recently proposed simulated annealing hyper-heuristic within a local search and genetic algorithm framework. The hybrid algorithm shows significant improvement over both the genetic algorithm with stochastic ranking and the simulated annealing hyper-heuristic alone. The hybrid algorithm also considerably outperforms the methods in the literature which have the previously best known results.

Anisotropic seismic inversion using a multigrid Monte Carlo approach

We propose a new approach for the inversion of anisotropic P-wave data based on Monte Carlo methods combined with a multigrid approach. Simulated annealing facilitates objective minimization of the functional characterizing the misfit between observed and predicted traveltimes, as controlled by the Thomsen anisotropy parameters (epsilon, delta). Cycling between finer and coarser grids enhances the computational efficiency of the inversion process, thus accelerating the convergence of the solution while acting as a regularization technique of the inverse problem. Multigrid perturbation samples the probability density function without the requirements for the user to adjust tuning parameters. This increases the probability that the preferred global, rather than a poor local, minimum is attained. Undertaking multigrid refinement and Monte Carlo search in parallel produces more robust convergence than does the initially more intuitive approach of completing them sequentially. We demonstrate the usefulness of the new multigrid Monte Carlo (MGMC) scheme by applying it to (a) synthetic, noise-contaminated data reflecting an isotropic subsurface of constant slowness, horizontally layered geologic media and discrete subsurface anomalies; and (b) a crosshole seismic data set acquired by previous authors at the Reskajeage test site in Cornwall, UK. Inverted distributions of slowness (s) and the Thomson anisotropy parameters (epsilon, delta) compare favourably with those obtained previously using a popular matrix-based method. Reconstruction of the Thomsen epsilon parameter is particularly robust compared to that of slowness and the Thomsen delta parameter, even in the face of complex subsurface anomalies. The Thomsen epsilon and delta parameters have enhanced sensitivities to bulk-fabric and fracture-based anisotropies in the TI medium at Reskajeage. Because reconstruction of slowness (s) is intimately linked to that epsilon and delta in the MGMC scheme, inverted images of phase velocity reflect the integrated effects of these two modes of anisotropy. The new MGMC technique thus promises to facilitate rapid inversion of crosshole P-wave data for seismic slownesses and the Thomsen anisotropy parameters, with minimal user input in the inversion process.

An ESPRIT-SAA-Based Detection Method for Broken Rotor Bar Fault in Induction Motors

This paper presents a novel detection method for broken rotor bar fault (BRB) in induction motors based on Estimation of Signal Parameters via Rotational Invariance Technique (ESPRIT) and Simulated Annealing Algorithm (SAA). The performance of ESPRIT is tested with simulated stator current signal of an induction motor with BRB. It shows that even with a short-time measurement data, the technique is capable of correctly identifying the frequencies of the BRB characteristic components but with a low accuracy on the amplitudes and initial phases of those components. SAA is then used to determine their amplitudes and initial phases and shows satisfactory results. Finally, experiments on a 3kW, 380V, 50Hz induction motor are conducted to demonstrate the effectiveness of the ESPRIT-SAA-based method in detecting BRB with short-time measurement data. It proves that the proposed method is a promising choice for BRB detection in induction motors operating with small slip and fluctuant load.

Cost dependent strategy for electricity markets bidding based on adaptive reinforcement learning

Electricity markets are complex environments, involving a large number of different entities, playing in a dynamic scene to obtain the best advantages and profits. MASCEM is a multi-agent electricity market simulator to model market players and simulate their operation in the market. Market players are entities with specific characteristics and objectives, making their decisions and interacting with other players. MASCEM provides several dynamic strategies for agents’ behavior. This paper presents a method that aims to provide market players with strategic bidding capabilities, allowing them to obtain the higher possible gains out of the market. This method uses a reinforcement learning algorithm to learn from experience how to choose the best from a set of possible bids. These bids are defined accordingly to the cost function that each producer presents.

Optimization techniques for power distribution planning with uncertainties: a comparative study

Important research effort has been devoted to the topic of optimal planning of distribution systems. The non linear nature of the system, the need to consider a large number of scenarios and the increasing necessity to deal with uncertainties make optimal planning in distribution systems a difficult task. Heuristic techniques approaches have been proposed to deal with these issues, overcoming some of the inherent difficulties of classic methodologies. This paper considers several methodologies used to address planning problems of electrical power distribution networks, namely mixedinteger linear programming (MILP), ant colony algorithms (AC), genetic algorithms (GA), tabu search (TS), branch exchange (BE), simulated annealing (SA) and the Bender´s decomposition deterministic non-linear optimization technique (BD). Adequacy of theses techniques to deal with uncertainties is discussed. The behaviour of each optimization technique is compared from the point of view of the obtained solution and of the methodology performance. The paper presents results of the application of these optimization techniques to a real case of a 10-kV electrical distribution system with 201 nodes that feeds an urban area.

Examination timetabling automation using hybrid meta-heuristics

Trabalho de projeto realizado para obtenção do grau de Mestre em Engenharia Informática e de Computadores

Design of New Materials for Passive Vibration Control

The objective of this contribution is to extend the models of cellular/composite material design to nonlinear material behaviour and apply them for design of materials for passive vibration control. As a first step a computational tool allowing determination of optimised one-dimensional isolator behaviour was developed. This model can serve as a representation for idealised macroscopic behaviour. Optimal isolator behaviour to a given set of loads is obtained by generic probabilistic metaalgorithm, simulated annealing. Cost functional involves minimization of maximum response amplitude in a set of predefined time intervals and maximization of total energy absorbed in the first loop. Dependence of the global optimum on several combinations of leading parameters of the simulated annealing procedure, like neighbourhood definition and annealing schedule, is also studied and analyzed. Obtained results facilitate the design of elastomeric cellular materials with improved behaviour in terms of dynamic stiffness for passive vibration control.

Design of New Materials for Passive Vibration Control

The aim of this contribution is to extend the techniques of composite materials design to non-linear material behaviour and apply it for design of new materials for passive vibration control. As a first step a computational tool allowing determination of macroscopic optimized one-dimensional isolator behaviour was developed. Voigt, Maxwell, standard and more complex material models can be implemented. Objective function considers minimization of the initial reaction and/or displacement peak as well as minimization of the steady-state amplitude of reaction and/or displacement. The complex stiffness approach is used to formulate the governing equations in an efficient way. Material stiffness parameters are assumed as non-linear functions of the displacement. The numerical solution is performed in the complex space. The steady-state solution in the complex space is obtained by an iterative process based on the shooting method which imposes the conditions of periodicity with respect to the known value of the period. Extension of the shooting method to the complex space is presented and verified. Non-linear behaviour of material parameters is then optimized by generic probabilistic meta-algorithm, simulated annealing. Dependence of the global optimum on several combinations of leading parameters of the simulated annealing procedure, like neighbourhood definition and annealing schedule, is also studied and analyzed. Procedure is programmed in MATLAB environment.

The fourth extracellular loop of the alpha subunit of Na,K-ATPase. Functional evidence for close proximity with the second extracellular loop.

Na,K-ATPase is the main active transport system that maintains the large gradients of Na(+) and K(+) across the plasma membrane of animal cells. The crystal structure of a K(+)-occluding conformation of this protein has been recently published, but the movements of its different domains allowing for the cation pumping mechanism are not yet known. The structure of many more conformations is known for the related calcium ATPase SERCA, but the reliability of homology modeling is poor for several domains with low sequence identity, in particular the extracellular loops. To better define the structure of the large fourth extracellular loop between the seventh and eighth transmembrane segments of the alpha subunit, we have studied the formation of a disulfide bond between pairs of cysteine residues introduced by site-directed mutagenesis in the second and the fourth extracellular loop. We found a specific pair of cysteine positions (Y308C and D884C) for which extracellular treatment with an oxidizing agent inhibited the Na,K pump function, which could be rapidly restored by a reducing agent. The formation of the disulfide bond occurred preferentially under the E2-P conformation of Na,K-ATPase, in the absence of extracellular cations. Using recently published crystal structure and a distance constraint reproducing the existence of disulfide bond, we performed an extensive conformational space search using simulated annealing and showed that the Tyr(308) and Asp(884) residues can be in close proximity, and simultaneously, the SYGQ motif of the fourth extracellular loop, known to interact with the extracellular domain of the beta subunit, can be exposed to the exterior of the protein and can easily interact with the beta subunit.