Structural models of algorithms in problems of applied programming. I. Formal algorithmic structures

A structural approach to modelling algorithms is proposed. The concept of an algorithmic structure with operations over algorithms is introduced. Models of algorithms constructed from algorithmic structures reflect aspects of algorithm representation and execution. Examples of structural and path models of algorithms are considered. Translated from Kibernetika i Sistemnyi Analiz, No. 3, pp. 3–14, May-June 2009.     

An approach to the parallel solution of a high-dimensional basic flow problem

The body of mathematics of modified systems of algorithmic algebras (SAA-M) is used to formalize the Edmonds–Karp algorithm of finding the maximum flow in a network. With allowance made for the distributed system features that are usually used for solving complicated problems, optimization criteria are formulated and used to obtain parallel SAA-M-schemes. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 146–152, March–April 2009.     

Transformational approach to the development of software architectures on the basis of fuzzy graph models

An approach to the creation of software architectures is examined that is based on the model-oriented paradigm that opens up the way to the implementation of transformational evolution of software systems. The emphasis is on the formalization of fuzzy graphs, fuzzy graph models, and rules of their transformation. A theoretical categorical representation of fuzzy software architectures is developed, which allows one to manage the process of their transformations on the basis of making decisions in a fuzzy modeling space on the functionality of the target platform-specific system. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 139–150, September–October 2008.     

An approach to expert assessment in software engineering

An approach is proposed to the solution of formalized problems of assessment of the activity that produces and maintains software systems (SSs). Such assessment is realized by using expertises that form a new assessment process adequate to the activity needs and specifics with an environment common to the expertises. The following mathematical apparatus is elaborated for expertises: a framework (target functions and executing mechanisms), a model and methods (formalisms for improving the quality and reusing the results of expertises) of an assessment process, and tools for integrating the apparatus into software development management processes. The approach is theoretically justified. Prospects of developing the proposed approach are described. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 151–168, July–August 2009.     

Improving quality of software product line by analysing inconsistencies in feature models using an ontological rule‐based approach

In software product line engineering, feature models (FMs) represent the variability and commonality of a family of software products. The development of FMs may introduce inaccurate feature relationships. These relationships may cause various types of defects such as inconsistencies, which deteriorate the quality of software products. Several researchers have worked on the identification of defects due to inconsistency in FMs, but only a few of them have explained their causes. In this paper, FM is transformed to predicate‐based feature model ontology using Prolog. Further, first‐order logic is employed for defining rules to identify defects due to inconsistency, the explanations for their causes, and suggestions for their corrections. The proposed approach is explained using an FM available in Software Product Line Online Tools repository. It is validated using 26 FMs of discrete sizes up to 5,543 features, generated using the FeatureIDE tool and real‐world FMs. Results indicate that the proposed methodology is effective, accurate, and scalable and improves software product line.     

Computer-based techniques for solving problems of applied and computational mathematics with given quality characteristics

The paper is concerned with computer-based techniques for the choice and development of computational resources and their efficient use to find an approximate solution with a given accuracy in a limited processor time. __________ Translated from Kibernetika i Sistemnyi Analiz, No. 5, pp. 33–41, September–October 2006.     

Formation and Development of Ideas of Artificial Intelligence in V. M. Glushkov’s Works

Ideas and means of artificial intelligence are considered that are developed in works of V. M. Glushkov and are used in brain modeling, computer-aided training, automata theory, and systems of algorithmic algebras.__________Translated from Kibernetika i Sistemnyi Analiz, No. 1, pp. 3–24, January–February 2005.     

Design optimization through parallel-generated surrogate models, optimization methodologies and the utility of legacy simulation software

This paper presents the motivation development and an application of a unique methodology to solve industrial optimization problems, using existing legacy simulation software programs. The methodology is based on approximation models generated with the utility of design of experiments methodologies and response surface methods applied on high-fidelity simulations, coupled together with classical optimization methodologies. Several DOE plans are included, in order to be able to adopt the appropriate level of detail. The approximations are based on stochastic interpolation techniques, or on classical least squares methods. The optimization methods include both local and global techniques. Finally, an application from the plastic molding industry (process simulation) demonstrates the methodology and the software package. Received December 30, 2000     

Optimality of software resource structurization in distributed processing

Efficiency and optimality criteria of block structurization of software resources taking account of overhead expenses is obtained for a class of uniformly distributed competing processes. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 59–62, November–December, 1999.     

Optimisation of algorithm control parameters in cultural differential evolution applied to molecular crystallography

Evolutionary search and optimisation algorithms have been used successfully in many areas of materials science and chemistry. In recent years, these techniques have been applied to, and revolutionised the study of crystal structures from powder diffraction data. In this paper we present the application of a hybrid global optimisation technique, cultural differential evolution (CDE), to crystal structure determination from powder diffraction data. The combination of the principles of social evolution and biological evolution, through the pruning of the parameter search space shows significant improvement in the efficiency of the calculations over traditional dictates of biological evolution alone. Results are presented in which a range of algorithm control parameters, i.e., population size, mutation and recombination rates, extent of culture-based pruning are used to assess the performance of this hybrid technique. The effects of these control parameters on the speed and efficiency of the optimisation calculations are discussed, and the potential advantages of the CDE approach demonstrated through an average 40% improvement in terms of speed of convergence of the calculations presented, and a maximum gain of 68% with larger population size.     

Embedding linear programming in multi objective genetic algorithms for reducing the size of the search space with application to leakage minimization in water distribution networks

This paper shows how embedding a local search algorithm, such as the iterated linear programming (LP), in the multi-objective genetic algorithms (MOGAs) can lead to a reduction in the search space and then to the improvement of the computational efficiency of the MOGAs. In fact, when the optimization problem features both continuous real variables and discrete integer variables, the search space can be subdivided into two sub-spaces, related to the two kinds of variables respectively. The problem can then be structured in such a way that MOGAs can be used for the search within the sub-space of the discrete integer variables. For each solution proposed by the MOGAs, the iterated LP can be used for the search within the sub-space of the continuous real variables. An example of this hybrid algorithm is provided herein as far as water distribution networks are concerned. In particular, the problem of the optimal location of control valves for leakage attenuation is considered. In this framework, the MOGA NSGAII is used to search for the optimal valve locations and for the identification of the isolation valves which have to be closed in the network in order to improve the effectiveness of the control valves whereas the iterated linear programming is used to search for the optimal settings of the control valves. The application to two case studies clearly proves the reduction in the MOGA search space size to render the hybrid algorithm more efficient than the MOGA without iterated linear programming embedded.     

DDoS攻击下Ad hoc网络队列管理算法研究与仿真

针对分布式拒绝服务攻击(DDoS)对于Ad hoc网络性能的影响进行了研究。在介绍三种经典网络队列管理算法——Drop-Tail、RED和REM的基础上,利用网络仿真软件NS2,分析比较了Ad hoc网络在遭受DDoS攻击时三种队列管理算法的防御能力。仿真表明,在中、轻度DDoS攻击下,主动式队列管理算法REM和RED较被动式队列管理算法Drop-Tail具有更强的防御能力,但在重度DDoS攻击下,三种队列管理算法性能均大幅下降。为有效提高Ad hoc网络对于DDoS攻击的防御能力,除采用主动式队列管理算法之外,应结合网络检测等其他防御机制。     

Structural elements of coordination mechanisms in collaborative planning processes and their assessment through maturity models: Application to a ceramic tile company

Maturity is defined as a measure to evaluate the capabilities of an organization in regards to a certain discipline. The Collaborative Planning Process is a very complex process and Coordination mechanisms are especially relevant in this field to align the plans of the supply chain members. The objective of this paper is to develop a maturity model and a methodology to perform assessment for the Structural Elements of Coordination Mechanisms in the Collaborative Planning Process. Structural elements are specified in order to characterize coordination mechanisms in a collaborative planning context and they have been defined as key areas to be assessed by the maturity model. The identified structural elements are: number of decision-makers, collaboration level, interdependence relationships nature, interdependence relationships type, number of coordination mechanisms, information exchanged, information processing, decision sequence characteristics and stopping criteria. Structural elements are assessed using the scheme of five levels: Initial, Repeatable, Defined, Managed and Optimized. This proposal has been applied to a ceramic tile company and the results are also reported.     

Genetic algorithm with advanced mechanisms applied to the protein structure prediction in a hydrophobic-polar model and cubic lattice

This paper presents a genetic algorithm applied to the protein structure prediction in a hydrophobic-polar model on a cubic lattice. The proposed genetic algorithm is extended with crowding, clustering, repair, local search and opposition-based mechanisms. The crowding is responsible for maintaining the good solutions to the end of the evolutionary process while the clustering is used to divide a whole population into a number of subpopulations that can locate different good solutions. The repair mechanism transforms infeasible solutions to feasible solutions that do not occupy the lattice point for more than one monomer. In order to improve convergence speed the algorithm uses local search. This mechanism improves the quality of conformations with the local movement of one or two consecutive monomers through the entire conformation. The opposition-based mechanism is introduced to transform conformations to the opposite direction. In this way the algorithm easily improves good solutions on both sides of the sequence. The proposed algorithm was tested on a number of well-known hydrophobic-polar sequences. The obtained results show that the mechanisms employed improve the algorithm's performance and that our algorithm is superior to other state-of-the-art evolutionary and swarm algorithms.     

A survey of models and algorithms for emergency response logistics in electric distribution systems. Part II: Contingency planning level

This is the second part of a two-part survey of optimization models and solution algorithms for emergency response planning in electric distribution systems. The first part of the survey addresses reliability planning problems with fault considerations related to electric distribution operations. The aim of this second part is to provide a comprehensive survey of optimization models and solution methodologies for contingency planning problems related to electric distribution operations. These problems include the restoration of service, the sequencing of switching operations, the routing of repair vehicles, the scheduling of repair crews, and the assignment of crews to repair sites.     

On a generalization of the Youla–Kučera parametrization. Part II: the lattice approach to MIMO systems

Within the lattice approach to analysis and synthesis problems recently developed in Quadrat (Signal Syst, to appear), we obtain a general parametrization of all stabilizing controllers for internally stabilizable multi input multi output (MIMO) plants which do not necessarily admit doubly coprime factorizations. This parametrization is a linear fractional transformation of free parameters and the set of arbitrary parameters is characterized. This parametrization generalizes for MIMO plants the parametrization obtained in Quadrat (Syst Control Lett 50:135–148, 2003) for single input single output plants. It is named general Q-parametrization of all stabilizing controllers as we show that some ideas developed in this paper can be traced back to the pioneering work of Zames and Francis (IEEE Trans Automat control 28:585-601, 1983) on H _∞-control. Finally, if the plant admits a doubly coprime factorization, we then prove that the general Q-parametrization becomes the well-known Youla-Kučera parametrization of all stabilizing controllers (Desoer et al. IEEE Trans Automat control 25:399–412, 1980; Vidyasagar, Control system synthesis: a factorization approach MIT Press, Cambridge 1985).     

Identification of nonlinear time-varying systems using an online sliding-window and common model structure selection (CMSS) approach with applications to EEG

The identification of nonlinear time-varying systems using linear-in-the-parameter models is investigated. An efficient common model structure selection (CMSS) algorithm is proposed to select a common model structure, with application to EEG data modelling. The time-varying parameters for the identified common-structured model are then estimated using a sliding-window recursive least squares (SWRLS) approach. The new method can effectively detect and adaptively track and rapidly capture the transient variation of nonstationary signals, and can also produce robust models with better generalisation properties. Two examples are presented to demonstrate the effectiveness and applicability of the new approach including an application to EEG data.     

Theory of Genetic Algorithms II: models for genetic operators over the string-tensor representation of populations and convergence to global optima for arbitrary fitness function under scaling

We present a theoretical framework for an asymptotically converging, scaled genetic algorithm which uses an arbitrary-size alphabet and common scaled genetic operators. The alphabet can be interpreted as a set of equidistant real numbers and multiple-spot mutation performs a scalable compromise between pure random search and neighborhood-based change on the alphabet level. We discuss several versions of the crossover operator and their interplay with mutation. In particular, we consider uniform crossover and gene-lottery crossover which does not commute with mutation. The Vose–Liepins version of mutation-crossover is also integrated in our approach. In order to achieve convergence to global optima, the mutation rate and the crossover rate have to be annealed to zero in proper fashion, and unbounded, power-law scaled proportional fitness selection is used with logarithmic growth in the exponent. Our analysis shows that using certain types of crossover operators and large population size allows for particularly slow annealing schedules for the crossover rate. In our discussion, we focus on the following three major aspects based upon contraction properties of the mutation and fitness selection operators: (i) the drive towards uniform populations in a genetic algorithm using standard operations, (ii) weak ergodicity of the inhomogeneous Markov chain describing the probabilistic model for the scaled algorithm, (iii) convergence to globally optimal solutions. In particular, we remove two restrictions imposed in Theorem 8.6 and Remark 8.7 of (Theoret. Comput. Sci. 259 (2001) 1) where a similar type of algorithm is considered as described here: mutation need not commute with crossover and the fitness function (which may come from a coevolutionary single species setting) need not have a single maximum.     

An architectural approach with separation of concerns to address extra-functional requirements in the development of embedded real-time software systems

A large proportion of the requirements on embedded real-time systems stems from the extra-functional dimensions of time and space determinism, dependability, safety and security, and it is addressed at the software level. The adoption of a sound software architecture provides crucial aid in conveniently apportioning the relevant development concerns. This paper takes a software-centered interpretation of the ISO 42010 notion of architecture, enhancing it with a component model that attributes separate concerns to distinct design views. The component boundary becomes the border between functional and extra-functional concerns. The latter are treated as decorations placed on the outside of components, satisfied by implementation artifacts separate from and composable with the implementation of the component internals. The approach was evaluated by industrial users from several domains, with remarkably positive results.