贪心遗传算法求解组合优化问题

许多问题最终可以归结为求解一个组合优化问题,GA是求解组合优化问题的一个强有力的工具,但遗传算法在应用中常出现收敛过慢和封闭竞争问题,本文提出贪心遗传算法。该算法的初始种群建立、交叉和变异等过程,都引入贪心选择策略指导搜索;移民操作向种群引进新的遗传物质,克服了封闭竞争缺点。贪心遗传算法可以避免早熟收敛并改进算法的性能,算法搜索起步阶段的效率是非常高的,本文通过TSP问题仿真试验证明了算法的有效性,在较少的计算量下,得到令人满意的结果。

Finding optimal alternatives based on efficient comparative preference inference

Choosing the right or the best option is often a demanding and challenging task for the user (e.g., a customer in an online retailer) when there are many available alternatives. In fact, the user rarely knows which offering will provide the highest value. To reduce the complexity of the choice process, automated recommender systems generate personalized recommendations. These recommendations take into account the preferences collected from the user in an explicit (e.g., letting users express their opinion about items) or implicit (e.g., studying some behavioral features) way. Such systems are widespread; research indicates that they increase the customers' satisfaction and lead to higher sales. Preference handling is one of the core issues in the design of every recommender system. This kind of system often aims at guiding users in a personalized way to interesting or useful options in a large space of possible options. Therefore, it is important for them to catch and model the user's preferences as accurately as possible. In this thesis, we develop a comparative preference-based user model to represent the user's preferences in conversational recommender systems. This type of user model allows the recommender system to capture several preference nuances from the user's feedback. We show that, when applied to conversational recommender systems, the comparative preference-based model is able to guide the user towards the best option while the system is interacting with her. We empirically test and validate the suitability and the practical computational aspects of the comparative preference-based user model and the related preference relations by comparing them to a sum of weights-based user model and the related preference relations. Product configuration, scheduling a meeting and the construction of autonomous agents are among several artificial intelligence tasks that involve a process of constrained optimization, that is, optimization of behavior or options subject to given constraints with regards to a set of preferences. When solving a constrained optimization problem, pruning techniques, such as the branch and bound technique, point at directing the search towards the best assignments, thus allowing the bounding functions to prune more branches in the search tree. Several constrained optimization problems may exhibit dominance relations. These dominance relations can be particularly useful in constrained optimization problems as they can instigate new ways (rules) of pruning non optimal solutions. Such pruning methods can achieve dramatic reductions in the search space while looking for optimal solutions. A number of constrained optimization problems can model the user's preferences using the comparative preferences. In this thesis, we develop a set of pruning rules used in the branch and bound technique to efficiently solve this kind of optimization problem. More specifically, we show how to generate newly defined pruning rules from a dominance algorithm that refers to a set of comparative preferences. These rules include pruning approaches (and combinations of them) which can drastically prune the search space. They mainly reduce the number of (expensive) pairwise comparisons performed during the search while guiding constrained optimization algorithms to find optimal solutions. Our experimental results show that the pruning rules that we have developed and their different combinations have varying impact on the performance of the branch and bound technique.

Domain decomposition using a 2-level correction scheme

The PHYSICA software was developed to enable multiphysics modelling allowing for interaction between Computational Fluid Dynamics (CFD) and Computational Solid Mechanics (CSM) and Computational Aeroacoustics (CAA). PHYSICA uses the finite volume method with 3-D unstructured meshes to enable the modelling of complex geometries. Many engineering applications involve significant computational time which needs to be reduced by means of a faster solution method or parallel and high performance algorithms. It is well known that multigrid methods serve as a fast iterative scheme for linear and nonlinear diffusion problems. This papers attempts to address two major issues of this iterative solver, including parallelisation of multigrid methods and their applications to time dependent multiscale problems.

A finite volume approach to geometrically non-linear stress analysis

In this past decade finite volume (FV) methods have increasingly been used for the solution of solid mechanics problems. This contribution describes a cell vertex finite volume discretisation approach to the solution of geometrically nonlinear (GNL) problems. These problems, which may well have linear material properties, are subject to large deformation. This requires a distinct formulation, which is described in this paper together with the solution strategy for GNL problem. The competitive performance for this procedure against the conventional finite element (FE) formulation is illustrated for a three dimensional axially loaded column.

ALES: a multi-mission adaptive sub-waveform retracker for coastal and open ocean altimetry

Satellite altimetry has revolutionized our understanding of ocean dynamics thanks to frequent sampling and global coverage. Nevertheless, coastal data have been flagged as unreliable due to land and calm water interference in the altimeter and radiometer footprint and uncertainty in the modelling of high-frequency tidal and atmospheric forcing. Our study addresses the first issue, i.e. altimeter footprint contamination, via retracking, presenting ALES, the Adaptive Leading Edge Subwaveform retracker. ALES is potentially applicable to all the pulse-limited altimetry missions and its aim is to retrack both open ocean and coastal data with the same accuracy using just one algorithm. ALES selects part of each returned echo and models it with a classic ”open ocean” Brown functional form, by means of least square estimation whose convergence is found through the Nelder-Mead nonlinear optimization technique. By avoiding echoes from bright targets along the trailing edge, it is capable of retrieving more coastal waveforms than the standard processing. By adapting the width of the estimation window according to the significant wave height, it aims at maintaining the accuracy of the standard processing in both the open ocean and the coastal strip. This innovative retracker is validated against tide gauges in the Adriatic Sea and in the Greater Agulhas System for three different missions: Envisat, Jason-1 and Jason-2. Considerations of noise and biases provide a further verification of the strategy. The results show that ALES is able to provide more reliable 20-Hz data for all three missions in areas where even 1-Hz averages are flagged as unreliable in standard products. Application of the ALES retracker led to roughly a half of the analysed tracks showing a marked improvement in correlation with the tide gauge records, with the rms difference being reduced by a factor of 1.5 for Jason-1 and Jason-2 and over 4 for Envisat in the Adriatic Sea (at the closest point to the tide gauge).

Quantum electronic transport in a configuration interaction basis

An overview of a many-body approach to calculation of electronic transport in molecular systems is given. The physics required to describe electronic transport through a molecule at the many-body level, without relying on commonly made assumptions such as the Landauer formalism or linear response theory, is discussed. Physically, our method relies on the incorporation of scattering boundary conditions into a many-body wavefunction and application of the maximum entropy principle to the transport region. Mathematically, this simple physical model translates into a constrained nonlinear optimization problem. A strategy for solving the constrained optimization problem is given. (C) 2004 Wiley Periodicals, Inc.

Epipolar geometry estimation based on evolutionary agents

This paper presents a novel approach based on the use of evolutionary agents for epipolar geometry estimation. In contrast to conventional nonlinear optimization methods, the proposed technique employs each agent to denote a minimal subset to compute the fundamental matrix, and considers the data set of correspondences as a 1D cellular environment, in which the agents inhabit and evolve. The agents execute some evolutionary behavior, and evolve autonomously in a vast solution space to reach the optimal (or near optima) result. Then three different techniques are proposed in order to improve the searching ability and computational efficiency of the original agents. Subset template enables agents to collaborate more efficiently with each other, and inherit accurate information from the whole agent set. Competitive evolutionary agent (CEA) and finite multiple evolutionary agent (FMEA) apply a better evolutionary strategy or decision rule, and focus on different aspects of the evolutionary process. Experimental results with both synthetic data and real images show that the proposed agent-based approaches perform better than other typical methods in terms of accuracy and speed, and are more robust to noise and outliers.

Power allocation strategies across N orthogonal channels for single-relay networks at both source and relay

We consider a wireless relay network with one source, one relay and one destination, where communications between nodes are preformed over N orthogonal channels. This, for example, is the case when orthogonal frequency division multiplexing is employed for data communications. Since the power available at the source and relay is limited, we study optimal power allocation strategies at the source and relay in order to maximize the overall source-destination capacity. Depending on the availability of the channel state information at both the source and relay or only at the relay, power allocation is performed at both the source and relay or only at the relay. Considering different setups for the problem, various optimization problems are formulated and solved. Some properties of the optimal solution are also proved.

A hybrid harmony search with arithmetic crossover operation for economic dispatch

Economic dispatch (ED) problems often exhibit non-linear, non-convex characteristics due to the valve point effects. Further, various constraints and factors, such as prohibited operation zones, ramp rate limits and security constraints imposed by the generating units, and power loss in transmission make it even more challenging to obtain the global optimum using conventional mathematical methods. Meta-heuristic approaches are capable of solving non-linear, non-continuous and non-convex problems effectively as they impose no requirements on the optimization problems. However, most methods reported so far mainly focus on a specific type of ED problems, such as static or dynamic ED problems. This paper proposes a hybrid harmony search with arithmetic crossover operation, namely ACHS, for solving five different types of ED problems, including static ED with valve point effects, ED with prohibited operating zones, ED considering multiple fuel cells, combined heat and power ED, and dynamic ED. In this proposed ACHS, the global best information and arithmetic crossover are used to update the newly generated solution and speed up the convergence, which contributes to the algorithm exploitation capability. To balance the exploitation and exploration capabilities, the opposition based learning (OBL) strategy is employed to enhance the diversity of solutions. Further, four commonly used crossover operators are also investigated, and the arithmetic crossover shows its efficiency than the others when they are incorporated into HS. To make a comprehensive study on its scalability, ACHS is first tested on a group of benchmark functions with a 100 dimensions and compared with several state-of-the-art methods. Then it is used to solve seven different ED cases and compared with the results reported in literatures. All the results confirm the superiority of the ACHS for different optimization problems.

Majorantes para a ordem de subgrafos induzidos k-regulares

Muitos dos problemas de otimização em grafos reduzem-se à determinação de um subconjunto de vértices de cardinalidade máxima que induza um subgrafo k-regular. Uma vez que a determinação da ordem de um subgrafo induzido k-regular de maior ordem é, em geral, um problema NP-difícil, são deduzidos novos majorantes, a determinar em tempo polinomial, que em muitos casos constituam boas aproximações das respetivas soluções ótimas. Introduzem-se majorantes espetrais usando uma abordagem baseada em técnicas de programação convexa e estabelecem-se condições necessárias e suficientes para que sejam atingidos. Adicionalmente, introduzem-se majorantes baseados no espetro das matrizes de adjacência, laplaciana e laplaciana sem sinal. É ainda apresentado um algoritmo não polinomial para a determinação de umsubconjunto de vértices de umgrafo que induz umsubgrafo k-regular de ordem máxima para uma classe particular de grafos. Finalmente, faz-se um estudo computacional comparativo com vários majorantes e apresentam-se algumas conclusões.

Implementing and testing branch-and-bound algorithm for the quadratic 0-1 problem on transputers

Discrete optimization problems are very difficult to solve, even if the dimention is small. For most of them the problem of finding an ε-approximate solution is already NP-hard. The branch-and-bound algorithms are the most used algorithms for solving exactly this sort of problems.

A computational study of a parallel Branch and Bound algorithm for the quadratic 0-1 programming problem on transputers

Discrete optimization problems are very difficult to solve, even if the dimantion is small. For most of them the problem of finding an ε-approximate solution is already NP-hard.

IP/optical integration in access network infrastructures: key issues on resource provisioning

This thesis contributes to the advancement of Fiber-Wireless (FiWi) access technologies, through the development of algorithms for resource allocation and energy efficient routing. FiWi access networks use both optical and wireless/cellular technologies to provide high bandwidth and ubiquity, required by users and current high demanding services. FiWi access technologies are divided in two parts. In one of the parts, fiber is brought from the central office to near the users, while in the other part wireless routers or base stations take over and provide Internet access to users. Many technologies can be used at both the optical and wireless parts, which lead to different integration and optimization problems to be solved. In this thesis, the focus will be on FiWi access networks that use a passive optical network at the optical section and a wireless mesh network at the wireless section. In such networks, two important aspects that influence network performance are: allocation of resources and traffic routing throughout the mesh section. In this thesis, both problems are addressed. A fair bandwidth allocation algorithm is developed, which provides fairness in terms of bandwidth and in terms of experienced delays among all users. As for routing, an energy efficient routing algorithm is proposed that optimizes sleeping and productive periods throughout the wireless and optical sections. To develop the stated algorithms, game theory and networks formation theory were used. These are powerful mathematical tools that can be used to solve problems involving agents with conflicting interests. Since, usually, these tools are not common knowledge, a brief survey on game theory and network formation theory is provided to explain the concepts that are used throughout the thesis. As such, this thesis also serves as a showcase on the use of game theory and network formation theory to develop new algorithms.

A aprendizagem da noção de derivada no 11º ano

Relatório da prática de ensino supervisionada, Mestrado em Ensino da Matemática, Universidade de Lisboa, 2014

Ant colony search algorithm for the optimal power flow problem

To maintain a power system within operation limits, a level ahead planning it is necessary to apply competitive techniques to solve the optimal power flow (OPF). OPF is a non-linear and a large combinatorial problem. The Ant Colony Search (ACS) optimization algorithm is inspired by the organized natural movement of real ants and has been successfully applied to different large combinatorial optimization problems. This paper presents an implementation of Ant Colony optimization to solve the OPF in an economic dispatch context. The proposed methodology has been developed to be used for maintenance and repairing planning with 48 to 24 hours antecipation. The main advantage of this method is its low execution time that allows the use of OPF when a large set of scenarios has to be analyzed. The paper includes a case study using the IEEE 30 bus network. The results are compared with other well-known methodologies presented in the literature.