**2. Characterization of NP-Complete problems**

In this section, the NP-Complete problems are presented as the main targets of GAs. Before starting to project a GA, it is of greatest importance to study and characterize the problem to justify the technique to use.

The early first notion of NP-completeness was proposed by Stephen Cook (1971), in his famous paper *The complexity of theorem proving procedures*. The main ideas presented in this section have their origins in the excelent works of Garey & Johnson (1979) and Papadimitriu (1995).

The Search for Parameters and Solutions:

incredible variety of possibilities for using GA tools.

emissivity behaviour of different dust grain species.

tool into a NP-complete problem and invert it.

**3.1 Using GA to model protoplanetary discs**

*protoplanetary discs* (Hetem & Gregorio-Hetem 2007).

from Class 0 to Class III, which is well established for TTs.

circumstellar parameters.

model.

**3.1.1 Presenting the problem**

luminosity, *L*; and temperature, *T*.

presented in Hetem & Gregorio-Hetem (2007).

Applying Genetic Algorithms on Astronomy and Engineering 163

data, like radio, infrared, visible and gamma-rays. All these solution constraints lead to an

In this section, it will be presented how GAs were used to model protoplanetary discs, an application that involves non-linear radiative-density profile relations. The model combines spectral energy distribution, observed in a wide range of the electromagnetic spectrum, and

Another interesting application is the use of GAs together with and spectral synthesis in the calculation of abundances and metallicities of T Tauri stars. In this problem, the model is outside the GA code, as one of the conditions imposed is to use a standard, well tested, spectral generator. It is presented how to deal with the challenge of changing a ready to use

This subsection is based on the published work *The use of genetic algorithms to model*

During its formation process, a young star object (YSO) can be surrounded by gas, dust grains and debris, that shall be gravitationally (and also electrostatically) agglomerate in the future solar system bodies. This material receives the energy brought from the star surface and re-irradiates it in other wavelengths. The contribution of this circumstellar matter to the spectral energy distribution (SED) slope is often used to recognize different categories of young YSOs by following an observational classification based on the near-infrared spectral index (Lada & Wilking 1984; Wilking, Lada & Young 1989; André, Ward-Thompson & Barsony 1993). Actually, this classification suggests a scenario for the evolution of YSOs,

Here, the adopted model is a flared configuration, according to Dullemond et al. (2001) modelling of a passively irradiated circumstellar disc with an inner hole. We used this model as the P-problem core of a GA based optimization method to estimate the

In this subsection we describe the implementation of the GA method for the flared-disc

The SED for a given set of parameters is evaluated according to Dullemond et al. (2001) model equations. The disc is composed by three components: the inner rim, the shadowed region, and the flared region with two layers: an illuminated hot layer and an inner cold layer. The disc parameters are: radius, *RD*; mass, *MD*; inclination, *θ*; density power law index, *p*; and inner rim temperature, *T*rim. The stellar parameters are: distance, *d*; mass, *M*;

The model starts by establishing a vertical boundary irradiated directly by the star, which considers the effect arising from shadowing from the rim, and the variations in scale height as a function of the radius. Figure 1 presents the obtained SED for the star AB Aurigae, as

Deep inside any GA code there is a model of the inverted problem to be solved. This routine works like I don't know what the correct answer is, but I kwon if a candidate to an answer is good or bad. So, the problem to be solved by a GA must have the property that any proposed solution to an instance must be quickly checked for correctness. For one thing, the solution must be concise, with length polynomially bounded by that of the instance.

To formalize the notion of quick checking, we will say that there is a polynomial-time algorithm that takes as input instance and the solution and decides whether or not it is a solution. If a problem demands a nondeterministic polynomial time to be solved, it is said a NP-problem, as defined by complexity theory researchers. It means that a solution to any search problem can be found and verified in polynomial time by nondeterministic algorithm.


**Part 3**

**Conservation of Germplasms**

310 Genetic Diversity in Plants

Umemoto, T., , Lin, H., Nakamura, Y., Inouchi, N., Sato, Y., Yano, M., Hirabayashi, H. &

Varavinit, S., Shobsngob, S., Varanyanond, W., Chinachoti, P. & Naivikul, O. (2003). Effect of

Wang, Z. Y., Zheng, F. Q., Shen, G. Z., Snustad, D. P., Li M. G., Zhang, J. L. & Hong, M. M.

Waters, D. L. E., Henry, R. J., Reinke, R. F. & Fitzgerald, M. A. (2006). Gelatinization

Xie, L., N., Chen, N., Duan, B., Zhu, Z. & Liao, X. (2008). Impact of proteins on pasting and

Yamakawa, H., Hirose, T., Kuroda, M. & Yamaguchi, T. (2007). Comprehensive expression

Yamamori, M., Fujita, S., Hayakawa, K., Matsuki, J. & Yasui, T. (2000). Genetic elimination

Yamanaka, S., Nakamura, I., Watanabe, K. N. & Sato, Y. (2004). Identification of SNPs in the

Yan, C., Li, X., Zhang, R., Sui, J. M., Liang, G. H., Shen, X. P., Gu, S. L. & Gu, M. H. (2005).

Yu, Y. & Wang, J. (2007). Effect of γ-ray irradiation on starch granule structure and

Zheng, X., Wu, J. G., Lou, X. Y. & Shi, C. H. (2007). The QTL analysis on maternal and

regulation of the *Waxy* gene. *Plant Journal*, Vol. 7, No. 4, pp. 613–622 Ward, R. M., Gao, Q., de Bruyn, H., Gilbert, R. G. G. & Fitzgerald, M. A. (2006). Improved

starch properties. *Functional Plant Biology*, Vol. 31, pp. 671–684

Vol. 165, No. 6, pp. 1193–1199

2, pp. 372–379

No. 7, pp. 1200–1204

Vol. 12, pp. 39–47

297-303

335–342

*Biomacromolecules*, Vol. 7, No. 3, pp. 866–876

*Biotechnology Journal*, Vol. 4, No. 1, pp. 115–122

microarray. *Plant Physiology*, Vol. 144, No. 1, pp. 258–277

Maruyama, S. (2004). Natural variation in rice *starch synthase IIa* affects enzyme and

amylose content on gelatinization, retrogradation and pasting properties of flours from different cultivars of Thai rice. *Starch - Stärke*, Vol. 55, No. 9, pp. 410–415 Wanchana, S., Toojinda, T., Tragoonrung, S. & Vanavichit A. (2003). Duplicated coding

sequence in the waxy allele of tropical glutinous rice (*Oryza sativa* L.). *Plant Science*,

(1995). The amylose content in rice endosperm is related to the post-transcriptional

methods for the structural analysis of the amylose-rich fraction from rice flour.

temperature of rice explained by polymorphisms in *starch synthase*. *Plant*

cooking properties of waxy and non-waxy rice. *Journal of Cereal Science*, Vol. 47, No.

profiling of rice grain filling-related genes under high temperature using DNA

of a starch granule protein, SGP-1, of wheat generates an altered starch with apparent high amylose. *Theoretical and Applied Genetics*, Vol. 101, No. 1–2, pp. 21–29

*waxy* gene among glutinous rice cultivars and their evolutionary significance during the domestication process of rice. *Theoretical and Applied Genetics*, Vol. 108,

Performance and inheritance of rice starch RVA profile characteristics. *Rice Science*,

physicochemical properties of rice. *Food Research International*, Vol. 40, No. 2, pp.

endosperm genome and their environmental interactions for characters of cooking quality in rice (*Oryza sativa* L.). *Theoretical and Applied Genetics*, Vol. 116, No. 3, pp.