Introduction

Although robust stability and control has been an active area of research since the 1970's [1,2,3], the Kharitonov approach to robust stability analysis is of more recent vintage [4]. Most existing work on robust stability analysis is based on relatively simple uncertainty structures and for systems with more complex uncertainty structures, these approaches are no longer feasible. Kharitonov's theorem for example [5], only applies to continuous-time systems with interval polynomials. Although the edge theorem relaxes Kharitonov's assumptions, the time complexity for this approach for a fixed order polynomial is O(n2^n-1), where n is the number of polytope edges [6]. Thus, it is not computationally tractable for even modestly large numbers of uncertain parameters. Zadeh provided an important tool known as the mapping theorem for testing the stability of polynomials with multilinear coefficients, but its time complexity for a fixed order polynomial is even worse ( O(2^2n-1)) [7].

Although there is no discrete analog of Kharitinov's theorem, robust Schur stability analysis has been widely investigated [4,1,8,9]. Unfortunately, the approaches in the literature are not in general applicable to polynomials with nonlinear uncertainty structures. The results can only be applied to non-linear uncertainty structures if overbounding is used, and provide a sufficient test for stability [4,10]. In general, the main approach for handling nonlinear uncertainty structures is by dense gridding of the uncertainty domain. In special cases, alternative approaches, such as the construction of the value sets using tree structured decomposition [10], are feasible. The questions of stability and stabilization of complex uncertain systems remain among the most important issues in control engineering today.

Recently, genetic algorithms (GAs) have been widely applied to effectively solve difficult optimization problems [11,12,13]. These algorithms have proven to be efficient for complex problems which are not computationally tractable using other approaches. GAs have attractive features for robust control problems because they do not require linearity, continuity, or other restrictions as in classical approaches. Furthermore, genetic algorithms offer the attraction that all parts of the feasible space are potentially available for exploration. This enhances the robustness properties of genetic search and the results obtainable for problems under investigation. Some researchers presented encouraging results by applying GAs to control parameter estimation [14,15,16], optimal control [17,18] and robust controller design [19,20,21,22,23]. To our knowledge, genetic algorithms have not been utilized for robust stability analysis of discrete-time uncertain systems. In this paper, we investigate the applicability and adaptability of GAs in providing a sufficient test of instability for such systems. We believe our instability test complements the overbounding stability test and provides a useful tool for investigating robustness.

The remainder of the paper is organized as follows. In Section 2 we give a framework for robust stability analysis of discrete-time systems. Section 3 describes the canonical genetic algorithm while section 4 describes our modifications to the canonical genetic algorithm for application to robust stability analysis. We present computational results and analysis in Section 5. Conclusions and directions for future studies are presented in Section 6.