Journal:Informatica
Volume 27, Issue 2 (2016), pp. 299–322
Abstract
We propose a heuristic global optimization technique which combines combinatorial and continuous local search. The combinatorial component, based on Reactive Search Optimization, generates a trajectory of binary strings describing search districts. Each district is evaluated by random sampling and by selective runs of continuous local search. A reactive prohibition mechanisms guarantees that the search is not stuck at locally optimal districts.
The continuous stochastic local search is based on the Inertial Shaker method: candidate points are generated in an adaptive search box and a moving average of the steps filters out evaluation noise and high-frequency oscillations.
The overall subdivision of the input space in a tree of non-overlapping search districts is adaptive, with a finer subdivision in the more interesting input zones, potentially leading to lower local minima.
Finally, a portfolio of independent CoRSO search streams (P-CoRSO) is proposed to increase the robustness of the algorithm.
An extensive experimental comparison with Genetic Algorithms and Particle Swarm demonstrates that CoRSO and P-CoRSO reach results which are fully competitive and in some cases significantly more robust.
Journal:Informatica
Volume 27, Issue 2 (2016), pp. 229–256
Abstract
This is a survey of the main achievements in the methodology and theory of stochastic global optimization. It comprises two complimentary directions: global random search and the methodology based on the use of stochastic models about the objective function. The main attention is paid to theoretically substantiated methods and mathematical results proven in the last 25 years.
Journal:Informatica
Volume 22, Issue 4 (2011), pp. 521–536
Abstract
A well-known example of global optimization that provides solutions within fixed error limits is optimization of functions with a known Lipschitz constant. In many real-life problems this constant is unknown.
To address that, we propose a novel method called Pareto–Lipschitzian Optimization (PLO) that provides solutions within fixed error limits for functions with unknown Lipschitz constants. In the proposed approach, a set of all unknown Lipschitz constants is regarded as multiple criteria using the concept of Pareto Optimality (PO).
We compare PLO to the existing algorithm DIRECT. We show that, in contrast to PLO, the DIRECT algorithm considers only a subset of PO decisions that are selected by a heuristic rule depending on an adjustable parameter. It means that some PO decisions are preferred to others. By contrast, PLO regards all PO decisions without preferences and is naturally suited to utilize highly parallel computing.
Journal:Informatica
Volume 21, Issue 1 (2010), pp. 149–158
Abstract
The optimization problems occurring in nonlinear regression normally cannot be proven unimodal. In the present paper applicability of global optimization algorithms to this problem is investigated with the focus on interval arithmetic based algorithms.
Journal:Informatica
Volume 19, Issue 3 (2008), pp. 447–460
Abstract
Multidimensional scaling is a technique for exploratory analysis of multidimensional data widely usable in different applications. By means of this technique the image points in a low-dimensional embedding space can be found whose inter-point distances fit the given dissimilarities between the considered objects. In this paper dependence of relative visualization error on the dimensionality of embedding space is investigated. Both artificial and practical data sets have been used. The images in three-dimensional embedding space normally show the structural properties of sets of considered objects with acceptable accuracy, and widening of applications of stereo screens makes three-dimensional visualization very attractive.
Journal:Informatica
Volume 19, Issue 1 (2008), pp. 45–62
Abstract
The aim is to investigate two emerging information technologies in graduate studies and scientific cooperation. Internet is the first technology. The open source is the second. They help each other in many ways. The joint influence of both is regarded in this paper.
Results of complexity theory show the limitations of exact analysis. That explains popularity of heuristic algorithms. It is well known that efficiency of heuristics depends on the parameters. Therefore automatic procedures for tuning the heuristics help to compare results of different heuristics and enhance their efficiency.
The theory and some applications of Bayesian Approach were discussed in (Mockus, 2006a). In this paper examples of Bayesian Approach to automated tuning of heuristics are investigated. This is the Bayesian Heuristic Approach, in short. The examples of traditional methods of optimization, including applications of linear and dynamic programming, will be investigated in the next paper. These three papers represents three parts of the same work. However each part can be read independently.
All the algorithms are implemented as platform independent Java applets or servlets. Readers can easily verify and apply the results for studies and for real life optimization problems.
The theoretical result is application of unified Bayesian Heuristic Approach for different discrete optimization models. The practical result is adaptation of these models for graduate distance studies and scientific collaboration by a common java global optimization framework.
The software is regularly updated and corrected responding to new programming tools and users reports. However the general structure of web sites remains. The information is on the web site: http://pilis.if.ktu.lt/~mockus and four mirror sites.
Journal:Informatica
Volume 17, Issue 2 (2006), pp. 259–278
Abstract
The objective is to investigate two emerging information technologies in graduate studies and scientific cooperation. Internet is the first technology. The open source is the second. They help each other in many ways. We investigate the joint influence of both.
Results of complexity theory show the limitations of exact analysis. That explains popularity of heuristic algorithms. It is well known that efficiency of heuristics depends on the parameters. Thus we need some automatic procedures for tuning the heuristics. That helps comparing results of different heuristics. This enhance their efficiency, too.
An initial presentation of the basic ideas is in (Mockus, 2000). Preliminary results of distance graduate studies are in (Mockus, 2006a). Examples of optimization of sequential statistical decisions are in (Mockus, 2006b).
In this paper the theory and applications of Bayesian Heuristic Approach are discussed. In the next paper examples of Bayesian Approach to automated tuning of heuristics will be regarded. The examples of traditional methods of optimization including applications of linear and dynamic programming will be investigated in the last paper. These papers represents three parts of the same work. However each part can be read independently.
All the algorithms are implemented as platform independent Java applets or servlets. Readers can easily verify and apply the results for studies and for real life optimization models.
The information is on the main web-site http://pilis.if.ktu.lt/∼jmockus and four mirrors.
Journal:Informatica
Volume 14, Issue 3 (2003), pp. 403–416
Abstract
The results of experimental testing of balanced random interval arithmetic with typical mathematical test functions and practical problem are presented and discussed. The possibility of evaluation ranges of functions using balanced random interval arithmetic is investigated. The influence of the predefined probabilities of standard and inner interval operations to the ranges of functions is experimentally investigated.
Journal:Informatica
Volume 14, Issue 1 (2003), pp. 121–130
Abstract
Recent publications on multidimensional scaling express contradicting opinion on multimodality of STRESS criterion. An example has been published with rigorously provable multimodality of STRESS. We present an example of data and the rigorous proof of multimodality of SSTRESS for this data. Some comments are included on widely accepted opinion that minimization of SSTRESS is easier than minimization of STRESS.
Journal:Informatica
Volume 13, Issue 3 (2002), pp. 311–332
Abstract
Real life scheduling problems are solved by heuristics with parameters defined by experts, as usual. In this paper a new approach is proposed where the parameters of various heuristics and their random mixtures are optimized to reduce the average deviations from the global optimum.
In many cases the average deviation is a stochastic and multi-modal function of heuristic parameters. Thus a stochastic global optimization is needed. The Bayesian heuristic approach is developed and applied for this optimization. That is main distinctive feature of this work. The approach is illustrated by flow-shop and school scheduling examples. Two versions of school scheduling models are developed for both traditional and profiled schools. The models are tested while designing schedules for some Lithuanian schools. Quality of traditional schedules is defined by the number of teacher “windows”. Schedules of profiled schools are evaluated by user defined penalty functions. That separates clearly subjective and objective data. This is the second specific feature of the proposed approach.
The software is developed for the Internet environment and is used as a tool for research collaboration and distance graduate studies. The software is available at web-sites and can be ran by standard net browsers supporting Java language. The care is taken that interested persons could easily test the results and apply the algorithms and software for their own problems.