# Evolutionary Methods in House Floor Plan Design
## 2 Visual Floor Plan Generation (VFPG) Framework
Thus, each room can be uniquely identified by a set of points \(P=\{p_{1},\ldots,p_{n}\}\) where \(p_{i}=(x,y)\in R^{2},l\leq i\leq n\in N\). Each point represents the place where the walls of the rooms meet. Hence, individuals in our approach use a representation of a real-valued point sequence. In order to interpret such a sequence as a valid space plan, a preprocessing _flood fill algorithm_[35] is applied to determine the connected areas that constitute a room. In this way, the individual phenotype I is created in the following way: \(I=\{R1\text{':}[p_{11}p_{12},\ldots,p_{1j_{1}}]\text{, }R2\text{':}[p_{21},\ldots,p_{2j_{2}}]\text{, }\ldots\text{, }Rk\text{':}[p_{k1},\ldots,p_{kj_{k}}]\text{,}\}\), where \(R1\), \(\ldots\), \(Rk\) denote recognized rooms and \([p_{m1},\ldots,p_{mj\_m}]\) is a sequence of points of all walls' connections in a room \(Rm\). The example floor plan, its simplified sketch with marked points and the actual representation are presented in Figure 3. Special points called _immobile_, which define the outline of the layout and as such cannot be changed by any evolutionary operation, are also indicated. **Initialization:** It is not trivial to generate the initial population where individuals are to fulfill all the constraints and meet the given requirements of architectural design. Therefore, at this stage of the algorithm, the designer domain knowledge is irreplaceable, and he or she explicitly points out a set of start-up solutions from the _Floor Plan Solutions Database_. Figure 2: The pseudocode of the proposed EP algorithm. **Fitness Evaluation:** The fitness of each individual _F(I)_ is measured as the individual's ability to fulfill all the constraints and the degree to which it achieves the objectives of the design task. There are different approaches to handle the constraints, like penalty functions or problem redefinition to an unconstrained one [36; 37]. We propose defining the mutation in such a way that most of the generated offspring are feasible, and if an unacceptable solution unfortunately occurs, it is rejected. The requirements \(Req_{i}(I)\in[0,1]\) (\(i=1,\ldots,n\)) have the _importance coefficients_ assigned such that \(w_{i}\) (\(i=1,\ldots,n\)), and the weighted sum of the degree to which they are achieved gives the final value of the fitness evaluation, which may be summarized as follows:  
\[F(I)=\left\{ \begin{array}{rl}&-\ \infty,\ \ \exists unfulfilled\ constraint\\ &\sum\limits_{i=1}^{n}w_{i}Req_{i}(I),\ \ otherwise\end{array} \right. \tag{1}\]  
**Mutation:** The mutation operation is the only procedure that introduces variation in a population. In the early generations, it should dynamically explore the search space, and when the space is sufficiently covered, it should allow for exploiting the obtained results to fine tune them. The exploration-exploitation trade-off in EP is moderated by strategy parameters. So far, the static strategy has been implemented, which is the simplest one, where the value of deviation is fixed and there is one strategy parameter per operator. However, it is straightforward that in the future, it will have to be dynamically changed over the generation time and over the individual fitness value. The following mutation operators have been defined: a new point can be added, a point can be deleted and a point can be moved. The operators may be applied individually with a given probability or in a randomly selected sequence. Since we assume that, in most cases, the mutation generates feasible solutions, some accompanying actions for every mutation operator has to be performed. When _adding a new point_, two situations have to be considered: a new point is (1) on the existing wall or (2) inside a room. In the first situation, an additional point has to be added, and there are at most two different ways to do that (see Figure 4A). In the second one, at least a further two points have to be included (see Figure 4B). _Deleting  
Figure 3: The example floor plan, its sketch with marked points and EP representation.